Jak obliczyć podstawę dziennika 2 w Javie dla liczb całkowitych?

138

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).

Nulldevice
źródło
1
Jak przetestowałeś to działanie? W moim systemie (Core i7, jdk 1.6 x64) wersja liczbowa jest prawie 10 razy szybsza niż wersja zmiennoprzecinkowa. Pamiętaj, aby faktycznie zrobić coś z wynikiem funkcji, aby JIT nie mógł całkowicie usunąć obliczenia!
x4u
Masz rację. Nie korzystałem z wyników obliczeń, a kompilator coś zoptymalizował. Teraz mam taki sam wynik jak Ty - funkcja liczb całkowitych jest 10 razy szybsza (Core 2 Duo, jdk 1,6 c64)
Nulldevice
6
To skutecznie daje Math.floor(Math.log(n)/Math.log(2)), więc tak naprawdę nie oblicza podstawy dziennika 2!
Dori

Odpowiedzi:

74

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ład Math.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:

static int pow(int base, int power) {
    int result = 1;
    for (int i = 0; i < power; i++)
        result *= base;
    return result;
}

private static void test(int base, int pow) {
    int x = pow(base, pow);
    if (pow != log(x, base))
        System.out.println(String.format("error at %d^%d", base, pow));
    if(pow!=0 && (pow-1) != log(x-1, base))
        System.out.println(String.format("error at %d^%d-1", base, pow));
}

public static void main(String[] args) {
    for (int base = 2; base < 500; base++) {
        int maxPow = (int) (Math.log(Integer.MAX_VALUE) / Math.log(base));
        for (int pow = 0; pow <= maxPow; pow++) {
            test(base, pow);
        }
    }
}

Jeśli użyjemy najprostszej implementacji logarytmu,

static int log(int x, int base)
{
    return (int) (Math.log(x) / Math.log(base));
}

to drukuje:

error at 3^5
error at 3^10
error at 3^13
error at 3^15
error at 3^17
error at 9^5
error at 10^3
error at 10^6
error at 10^9
error at 11^7
error at 12^7
...

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.

Rotsor
źródło
3
„to nie znaczy, że będzie działać w ten sam sposób na każdym komputerze” - tak by się stało, gdybyś użył strictfp, nie?
Ken
@Ken: Może ... Ale możesz być pewien tylko po wyczerpującym wyliczeniu wszystkich możliwych wartości wejściowych. (mamy szczęście, że jest ich tu tak mało)
Rotsor
2
Technicznie tak, ale dotyczy to każdej funkcji. W pewnym momencie musisz ufać, że jeśli użyjesz dostępnej dokumentacji i przetestujesz dobrze dobrany, ale znikomo mały ułamek "wszystkich możliwych wartości wejściowych", twój program będzie działał wystarczająco dobrze. strictfpwydaje się, że dostał wiele bzdur za bycie surowym. :-)
Ken
jak return ((long)Math.log(x) / (long)Math.log(base));rozwiązać wszystkie błędy?
To nie jest błąd,
92

Oto funkcja, której używam do tego obliczenia:

public static int binlog( int bits ) // returns 0 for bits=0
{
    int log = 0;
    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
    if( bits >= 256 ) { bits >>>= 8; log += 8; }
    if( bits >= 16  ) { bits >>>= 4; log += 4; }
    if( bits >= 4   ) { bits >>>= 2; log += 2; }
    return log + ( bits >>> 1 );
}

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:

private static final double log2div = 1.000000000001 / Math.log( 2 );
public static int log2fp0( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return (int) ( Math.log( bits & 0xffffffffL ) * log2div );
}

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ż binlogpowyższa. Niestety, JIT klienta nie wydaje się mieć takiej optymalizacji.

public static int log2nlz( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return 31 - Integer.numberOfLeadingZeros( bits );
}

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:

binlog:         11.5s
log2nlz:        16.5s
log2fp:        118.1s
log(x)/log(2): 165.0s

Maszyna wirtualna serwera JDK 1.7 x64:

binlog:          5.8s
log2nlz:         5.1s
log2fp:         89.5s
log(x)/log(2): 108.1s

Oto kod testu:

int sum = 0, x = 0;
long time = System.nanoTime();
do sum += log2nlz( x ); while( ++x != 0 );
time = System.nanoTime() - time;
System.out.println( "time=" + time / 1000000L / 1000.0 + "s -> " + sum );
x4u
źródło
9
BSRInstrukcja x86 tak 32 - 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ą numberOfLeadingZerosdokładnie, w jednej instrukcji. Oba mają 3 cykle opóźnienia, 1 na cykl. Więc zdecydowanie polecam używanie numberOfLeadingZeros, ponieważ to ułatwia stworzenie dobrego JVM. (Jedyną dziwną rzeczą lzcntjest to, że ma fałszywą zależność od starej wartości rejestru, który nadpisuje.)
Peter Cordes
Najbardziej interesuje mnie twój komentarz dotyczący zamienników wewnętrznych procesorów JIT CPU w serwerze Java 1.7. Czy masz adres URL odniesienia? (Link do kodu źródłowego JIT jest również w porządku.)
kevinarpe
37

Próbować Math.log(x) / Math.log(2)

Chris B.
źródło
8
Chociaż matematycznie jest to poprawne, należy pamiętać, że istnieje ryzyko błędnych obliczeń z powodu nieprecyzyjnej arytmetyki zmiennoprzecinkowej, jak wyjaśniono w odpowiedzi Rotsora.
leeyuiwah
28

możesz użyć tożsamości

            log[a]x
 log[b]x = ---------
            log[a]b

więc miałoby to zastosowanie do log2.

            log[10]x
 log[2]x = ----------
            log[10]2

po prostu podłącz to do metody log10 java Math ....

http://mathforum.org/library/drmath/view/55565.html

hvgotcodes
źródło
3
Chociaż matematycznie jest to poprawne, należy pamiętać, że istnieje ryzyko błędnych obliczeń z powodu nieprecyzyjnej arytmetyki zmiennoprzecinkowej, jak wyjaśniono w odpowiedzi Rotsora.
leeyuiwah
18

Dlaczego nie:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}
TofuBeer
źródło
6
Chociaż matematycznie jest to poprawne, należy pamiętać, że istnieje ryzyko błędnych obliczeń z powodu nieprecyzyjnej arytmetyki zmiennoprzecinkowej, jak wyjaśniono w odpowiedzi Rotsora.
leeyuiwah
9

W bibliotekach guawy jest funkcja:

LongMath.log2()

Więc proponuję go użyć.

Demetr
źródło
Jak mogę dodać ten pakiet do mojej aplikacji?
Elvin Mammadov,
Pobierz słoik stąd i dodaj go do ścieżki kompilacji projektu.
Debosmit Ray
2
Czy powinienem dodać bibliotekę do mojej aplikacji tylko po to, aby używać jednej funkcji?
Tash Pemhiwa
7
Dlaczego właściwie miałbyś go sugerować? Szybkie przeczytanie źródła Guava pokazuje, że robi to samo, co metoda OP (kilka bardzo dobrze zrozumiałych wierszy kodu), kosztem dodania bezużytecznej zależności. To, że Google coś zapewnia, nie czyni tego lepszym niż zrozumienie problemu i samodzielne rozwiązanie.
Dave
3

Aby dodać do odpowiedzi x4u, która daje dolną część logu binarnego liczby, ta funkcja zwraca górną wartość logu binarnego liczby:

public static int ceilbinlog(int number) // returns 0 for bits=0
{
    int log = 0;
    int bits = number;
    if ((bits & 0xffff0000) != 0) {
        bits >>>= 16;
        log = 16;
    }
    if (bits >= 256) {
        bits >>>= 8;
        log += 8;
    }
    if (bits >= 16) {
        bits >>>= 4;
        log += 4;
    }
    if (bits >= 4) {
        bits >>>= 2;
        log += 2;
    }
    if (1 << log < number)
        log++;
    return log + (bits >>> 1);
}
Ofek Ron
źródło
Gdzie jest zmienna „liczba”?
barteks2x
3

Niektóre przypadki po prostu działały, gdy korzystałem z Math.log10:

public static double log2(int n)
{
    return (Math.log10(n) / Math.log10(2));
}
przystań
źródło
0

dodajmy:

int[] fastLogs;

private void populateFastLogs(int length) {
    fastLogs = new int[length + 1];
    int counter = 0;
    int log = 0;
    int num = 1;
    fastLogs[0] = 0;
    for (int i = 1; i < fastLogs.length; i++) {
        counter++;
        fastLogs[i] = log;
        if (counter == num) {
            log++;
            num *= 2;
            counter = 0;
        }
    }
}

Źródło: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

Guido Celada
źródło
To byłoby utworzenie tabeli przeglądowej. OP poprosił o szybszy sposób „obliczania” logarytmu.
Dave
-4

Aby obliczyć logarytm o podstawie 2 n, można użyć następującego wyrażenia:

double res = log10(n)/log10(2);
Akanksha
źródło
2
Ta odpowiedź została już opublikowana kilka razy i została już zauważona jako potencjalnie niedokładna z powodu błędu zaokrąglenia. Zwróć uwagę na OP, w którym zapytano o wartość całkowitą; nie jest wcale jasne, jakiej dokładności zaokrąglania należy użyć, aby uzyskać stąd liczbę całkowitą.
AnotherParker