Zmarchtwychwstałem ;)
Zna ktoś bibliotekę matematyczną (najlepiej w Javie), która potrafi rozwiązać taki problem. Dane są dwie liczby: b z przedziału (0;1) oraz a trochę mniejsza niż 1 Wyznaczyć najmniejszą liczbę naturalną n taką, a^n <= b. Zadanie nie jest trywialne: przykładowe dane, dla których interesuje mnie rozwiązanie:
b = 0,1
a = 0,9999999999999999999999999999999999999999990667378455605584731830076114373329950928403173561837853141
Nie wymagam zapisu dziesiętnego liczby n, wystarczy postać 2^k (ewentualnie 2^(2^k)) i zapis dziesiętny liczby k.
0
0
To będą jakieś straszne iteracje, polecam coś szybszego niż Java, może https://gmplib.org/?
0
Nie jest tak strasznie, jestem już prawie u celu. Potrafię (w ułamku sekundy) obliczyć wartość a^n, dla podanych przykładowych wartości jest to:
0.09999999999999999999999999999999999999999998871583867979635063144093639055550751333783490792172181566
i (chyba) wiem jak z wykonywanych rachunków wydobyć wartość n.
0
Czy to jest jakieś zadanie ze SPOJ? Jak tak daj linka :)
bogdans napisał(a):
Nie jest tak strasznie, jestem już prawie u celu. Potrafię (w ułamku sekundy) obliczyć wartość a^n, dla podanych przykładowych wartości jest to:
0.09999999999999999999999999999999999999999998871583867979635063144093639055550751333783490792172181566
i (chyba) wiem jak z wykonywanych rachunków wydobyć wartość n.
Skoro potrafisz liczyć a^n to znasz n, czyli po co jeszcze to wydobywać. Chyba, że masz na myśli wydobycie tego minimalnego n spełniającego nierówność - pisz precyzyjnie.
Osobiście, próbowałbym robić wyszukiwanie binarne w przestrzeni n. Założyłbym jakiś wielki przedział np. n = [1, 1 000 000 000 000] i zaczął od połowy przedziału i szedł rekurencyjnie góra / dół.
0
To nie jest problem ze SPOJa :).
Może Ci wyjaśnię jak obliczam wymagane a^n bez obliczania n:
//edit algorytm trochę uprościłem i zmodyfikowałe,
Pierwszy krok: liczę potęgi a^2, a^4, a^8, ... aż minę b (kolejny wyraz ciągu jest kwadratem poprzedniego). Niech c oznacza przedostatni wyraz ciągu.
Drugi krok: tworzę ciąg c.a^2, c.a^4, c.a^8, ... aż minę b (kolejny mnożnik jest kwadratem poprzedniego, kropki zastępują znaki mnożenia - nie umiałem ich napisać). Niech c oznacza przedostatni wyraz ciągu.
Trzeci krok jest identyczny z drugim.
...
Kończę, gdy pętla jest jednoelementowa.
0
Jaką to ma przewagę nad pętlą gdzie robisz:
a, b;
pow = a
n = 1;
while(pow <= b){
n++
pow = pow * a
}
return n-1
0
Ty serio pytasz? Suma długości moich pętli wynosi (przy podanych wartościach a i b): 5093.
0
Wolfram Alpha podaje n = 2.1604 x 10^14
To zadanie raczej musisz rozwiązywać symbolicznie niż iteracyjnie, bo przy takiej liczbie cyfr szybko tracisz dokładność.
Przejrzyj to poniżej i daj znać co wybrałeś:
https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software
https://en.wikipedia.org/wiki/List_of_numerical_libraries#Java
0
Zostanę przy standardowej bibliotece Javy (BigInteger i BigDecimal), wyniki mam w ułamku sekundy. Aczkolwiek mój wynik jest zupełnie różny od tego, który Ty podałeś, Mój wynik to, w przybliżeniu 2.467x10^42.
Na razie ufam swojej metodzie, dla liczb a bardziej odległych od 1 (np. 0.9999999999987116839024895291346349005305189215225010982834209369861179438034316249082014864732670347) użyłem Pythona do sprawdzenia uzyskanego wyniku, potwierdził. Dla liczby a z pierwszego postu Python jest nieprzydatny: i dla typu float i dla typu Decimal nie odróżnia tej liczby od 1.
0
Nie wiem, które rozwiązanie lepsze, wiem tylko że Wolfram potrafi generować liczby z kosmiczną dokładnością.
BigDecimala też miałem zasugerować bo jak coś jest w bibliotece standardowej to warto spróbować.
Jak byś został trochę dłużej przy Javie, to znalazłem przy okazji ciekawą książkę:
https://www.amazon.com/Java-Number-Cruncher-Programmers-Numerical/dp/0130460419
i coś z czym trzeba chyba poczekać do następnej promocji na Springer (była w tym tygodniu - ebooki po $7):
https://www.amazon.com/Computation-Statistical-Information-Knowledge-Processing-ebook/dp/B01DD9ATRI/
0
Nie znalazłem u Wolframa odpowiedniego liczydła.
Uruchom ten kod (na Ideone wywala się po 67 wierszu):
import java.math.BigDecimal;
import java.math.MathContext;
class Powers
{
public static void main(String[] args)
{
int PRECISION = 1000;
MathContext mc = new MathContext(PRECISION);
BigDecimal number = new BigDecimal("0.9999999999999999999999999999999999999999990667378455605584731830076114373329950928403173561837853141", mc);
for(int n = 1; n < 150; n++)
{
number = number.multiply(number, mc);
System.out.println(n + "." + number);
}
}
}
W k-tym wierszu wyświetlana jest potęga number^(2^k). Dopiero dla k = 141 wartość potęgi jest mniejsza niż 0.1 a 2^141 jest dużym przybliżeniu równe 10^47 .
0
bogdans napisał(a):
Nie znalazłem u Wolframa odpowiedniego liczydła.
Ja też nie za dobrze znam to narzędzie, ale jak wprowadzisz poniższe wyrażenie to Wolfram zdaje się to rozumieć:
0.9999999999999999999999999999999999999999990667378455605584731830076114373329950928403173561837853141^n<=0.1
Wynik masz w sekcji "real solution".
0
Wpisz 0.9999999999999999999999999999999999999999990667378455605584731830076114373329950928403173561837853141^(2.1604*10^14)) i zobacz odpowiedź..
0
Najwidoczniej to nie działa tak jak myślałem. Metodą prób i błędów daje się oszacować na Wolframie liczbę n między 10^42 a 10^43.
0
Obawiam się, że jest gorzej. W intencji twórców działa tak jak myślisz, tylko obliczenia są błędne (bardzo niedokładne).
0.999^n<=0.1 => n>=2301.43
0.999^2301.43 => 0.100000361028141...
0
Teoretycznie to powinno zadziałać:
Minimize[{0.999^x <= 0.1, x > 0 && Element[x, Integers]}, x]
zgodnie z tym:
https://reference.wolfram.com/language/ref/Minimize.html
ale aktualnie coś się zwiesiło, a ja lecę do pracy...
0
Wydaje mi się, że to problem podobny do liczenia "rozsplotu" w dziedzinie czasu, wynik n-tego wyrazu zależy od n-1, i dość szybko błędy obliczeń powodują efekt motyla. Przy założeniu, że a ma k = 100 cyfr po przecinku to potęga a^2 podwaja precyzję wyniku. więc a^n daje coś k^(n/2) cyfr po przecinku, wiec dla n=10^47 potrzebujesz precyzji ... 10^47!!!, aż strach się bać. Przy stałej precyzji 1000 cyfr, tak jak zwrócił uwagę @vpiotr, już po 4 iteracjach potrzebujesz 1600 cyfr po przecinku. Dalsze obliczenia to już zaokrąglenia zaokrągleń.
1
Ja bym do tego najpierw podszedł analitycznie:
Teraz a - 1 można w miarę dokładnie przedstawić w zwykłym typie zmiennoprzecinkowym, b też, więc można uzyskać dość dokładną estymację n:
Teraz pozostaje ustalić jak dokładny wynik można dzięki temu uzyskać i może się okazać, że precyzja jest dostatecznie duża.
Jeśli nie to przynajmniej wiadomo gdzie szukać rozwiązania dokładnego.
0
Ja kombinowałem analitycznie podobnie, ale w pewnym momencie temat zaparkowałem.
- a^n <= b i a,b in (0,1)
i) Dla a<=b => Trywialne, n=1
ii) Interesujace sa przypadki: a>b
-
Dla a z (0,1) :
i) a^x jest malejaca
ii) log_a(x) jest malejąca -
Logarytmujemy obustronnie logarytmem o podstawie a i zamieniamy na logarytm naturalny
n >= log_a{b} = ln(b) / ln(a)
- Ln(a) = Calka(0,a)(dt/t)
Czyli n>= Calka(0,b)(dt/t) / Calka(0,a)(dt/t)
Jak weźmiemy rozkłąd jednostajny U(0,a), to on ma:
a) średnią: a/2
b) wariancję: a^2/12
1/a * calka{0,a} {1/t}td to nic innego jak wartość oczekiwana EF(X) dla F(X)=1/X i X z rozkładu jednostajnego (0,a)
Tu myślałem, żeby ten logarytm wyliczyć jakoś metodami monte carlo i mieć nadzieję, że istotna będzie tylko precyzja dla dzielenia logarytmów.
Druga ścieżka "analityczna", to było rozwijanie f(X)=1/X względem momentów centralnych rozkładu prawdopodobieństwa:
Ef(X) = f(m) + f'(m)(X-m)/1! + f''(m)(X-m)^2/2! + f'''(m)(X-m)^3/3! + ... =
(gdzie m to średnia rozkładu jednostajnego)
0
Dziękuje za wskazówki, ale problem już rozwiązałem. Napisałem wcześniej, że umiem wyliczyć a^n bez wyznaczania tego n i wiem (chyba) jak z moich rachunków wydobyć n. Nie napisałem, za co przepraszam, że umiem to n wydobyć. Dla a i b z pierwszego postu n = 2467243616427454940153538822421803056235192 (w jednym z postów napisałem, że n równa się w przybliżeniu 2.467x10^42, co mogło sugerować, że wiem jak rozwiązać problem).