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

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

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.

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

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

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

Dlaczego nie:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}

W bibliotekach guawy jest funkcja:

LongMath.log2()

Więc proponuję go użyć.

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);
}

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));
}

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

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

double res = log10(n)/log10(2);