Używam następującej funkcji do obliczenia podstawy logu 2 dla liczb całkowitych:
public static int log2(int n){
if(n <= 0) throw new IllegalArgumentException();
return 31 - Integer.numberOfLeadingZeros(n);
}
Czy ma optymalną wydajność?
Czy ktoś zna gotową funkcję J2SE API do tego celu?
UPD1 Zaskakująco dla mnie arytmetyka zmiennoprzecinkowa wydaje się być szybsza niż arytmetyka liczb całkowitych.
UPD2 Ze względu na uwagi przeprowadzę bardziej szczegółowe dochodzenie.
UPD3 Moja funkcja arytmetyczna liczb całkowitych jest 10 razy szybsza niż Math.log (n) /Math.log (2).
java
performance
discrete-mathematics
logarithm
Nulldevice
źródło
źródło
Math.floor(Math.log(n)/Math.log(2))
, więc tak naprawdę nie oblicza podstawy dziennika 2!Odpowiedzi:
Jeśli myślisz o użyciu liczb zmiennoprzecinkowych do pomocy w arytmetyce liczb całkowitych, musisz być ostrożny.
Zwykle staram się unikać obliczeń FP, gdy tylko jest to możliwe.
Operacje zmiennoprzecinkowe nie są dokładne. Nigdy nie możesz wiedzieć na pewno, co zostanie
(int)(Math.log(65536)/Math.log(2))
ocenione. Na przykładMath.ceil(Math.log(1<<29) / Math.log(2))
na moim komputerze jest 30, podczas gdy matematycznie powinno być dokładnie 29. Nie znalazłem wartości dla x, gdzie(int)(Math.log(x)/Math.log(2))
zawodzi (tylko dlatego, że są tylko 32 „niebezpieczne” wartości), ale nie oznacza to, że zadziała tak samo na każdym komputerze.Typowa sztuczka polega na używaniu „epsilon” podczas zaokrąglania. Nie
(int)(Math.log(x)/Math.log(2)+1e-10)
powinno nigdy zawieść. Wybór tego „epsilonu” nie jest łatwym zadaniem.Więcej demonstracji, używając bardziej ogólnego zadania - próba wdrożenia
int log(int x, int base)
:Kod testowy:
Jeśli użyjemy najprostszej implementacji logarytmu,
to drukuje:
Aby całkowicie pozbyć się błędów musiałem dodać epsilon, który jest między 1e-11 a 1e-14. Czy mogłeś to powiedzieć przed testowaniem? Zdecydowanie nie mogłem.
źródło
strictfp
, nie?strictfp
wydaje się, że dostał wiele bzdur za bycie surowym. :-)return ((long)Math.log(x) / (long)Math.log(base));
rozwiązać wszystkie błędy?Oto funkcja, której używam do tego obliczenia:
Jest nieco szybszy niż Integer.numberOfLeadingZeros () (20-30%) i prawie 10 razy szybszy (jdk 1,6 x64) niż implementacja oparta na Math.log (), taka jak ta:
Obie funkcje zwracają te same wyniki dla wszystkich możliwych wartości wejściowych.
Aktualizacja: JIT serwera Java 1.7 jest w stanie zastąpić kilka statycznych funkcji matematycznych alternatywnymi implementacjami opartymi na elementach procesora. Jedną z tych funkcji jest Integer.numberOfLeadingZeros (). Tak więc w przypadku maszyny wirtualnej serwera w wersji 1.7 lub nowszej implementacja taka jak ta, o której mowa, jest w rzeczywistości nieco szybsza niż
binlog
powyższa. Niestety, JIT klienta nie wydaje się mieć takiej optymalizacji.Ta implementacja zwraca również te same wyniki dla wszystkich 2 ^ 32 możliwych wartości wejściowych, co pozostałe dwie implementacje, które opublikowałem powyżej.
Oto rzeczywiste środowiska wykonawcze na moim komputerze (Sandy Bridge i7):
JDK 1.7 32-bitowa maszyna wirtualna klienta:
Maszyna wirtualna serwera JDK 1.7 x64:
Oto kod testu:
źródło
BSR
Instrukcja x86 tak32 - numberOfLeadingZeros
, ale niezdefiniowana dla 0, więc kompilator (JIT) musi sprawdzić, czy nie ma wartości niezerowej, jeśli nie może udowodnić, że nie musi. Wprowadzono rozszerzenia zestawu instrukcji BMI (Haswell i nowsze)LZCNT
, które w pełni implementująnumberOfLeadingZeros
dokładnie, w jednej instrukcji. Oba mają 3 cykle opóźnienia, 1 na cykl. Więc zdecydowanie polecam używanienumberOfLeadingZeros
, ponieważ to ułatwia stworzenie dobrego JVM. (Jedyną dziwną rzecząlzcnt
jest to, że ma fałszywą zależność od starej wartości rejestru, który nadpisuje.)Próbować
Math.log(x) / Math.log(2)
źródło
możesz użyć tożsamości
więc miałoby to zastosowanie do log2.
po prostu podłącz to do metody log10 java Math ....
http://mathforum.org/library/drmath/view/55565.html
źródło
Dlaczego nie:
źródło
W bibliotekach guawy jest funkcja:
Więc proponuję go użyć.
źródło
Aby dodać do odpowiedzi x4u, która daje dolną część logu binarnego liczby, ta funkcja zwraca górną wartość logu binarnego liczby:
źródło
Niektóre przypadki po prostu działały, gdy korzystałem z Math.log10:
źródło
dodajmy:
Źródło: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java
źródło
Aby obliczyć logarytm o podstawie 2 n, można użyć następującego wyrażenia:
źródło