Wie berechnet man Log Base 2 in Java für ganze Zahlen?

138

Ich benutze die folgende Funktion, um die Protokollbasis 2 für ganze Zahlen zu berechnen:

public static int log2(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
}

Hat es eine optimale Leistung?

Kennt jemand die J2SE-API-Funktion für diesen Zweck?

UPD1 Überraschenderweise scheint die Gleitkomma- Arithmetik für mich schneller zu sein als die Ganzzahl-Arithmetik.

UPD2 Aufgrund von Kommentaren werde ich detailliertere Untersuchungen durchführen.

UPD3 Meine ganzzahlige arithmetische Funktion ist zehnmal schneller als Math.log (n) /Math.log (2).

Nullgerät
quelle
1
Wie haben Sie die Leistung getestet? Auf meinem System (Core i7, jdk 1.6 x64) ist die Ganzzahlversion fast zehnmal schneller als die Gleitkommaversion. Stellen Sie sicher, dass Sie tatsächlich etwas mit dem Ergebnis der Funktion tun, damit die JIT die Berechnung nicht vollständig entfernen kann!
x4u
Du hast Recht. Ich habe keine Berechnungsergebnisse verwendet und der Compiler hat etwas optimiert. Jetzt habe ich das gleiche Ergebnis wie Sie - die Ganzzahlfunktion ist zehnmal schneller (Core 2 Duo, jdk 1.6 c64)
Nulldevice
6
Dies gibt Ihnen effektiv Math.floor(Math.log(n)/Math.log(2)), so dass es nicht wirklich Log Base 2 berechnet!
Dori

Antworten:

74

Wenn Sie darüber nachdenken, Gleitkommawerte für die Ganzzahlarithmetik zu verwenden, müssen Sie vorsichtig sein.

Normalerweise versuche ich, FP-Berechnungen nach Möglichkeit zu vermeiden.

Gleitkommaoperationen sind nicht genau. Sie können nie sicher wissen, was zu (int)(Math.log(65536)/Math.log(2))bewerten ist. Zum Beispiel Math.ceil(Math.log(1<<29) / Math.log(2))ist 30 auf meinem PC, wo es mathematisch genau 29 sein sollte. Ich habe keinen Wert für x gefunden, wo (int)(Math.log(x)/Math.log(2))fehlschlägt (nur weil es nur 32 "gefährliche" Werte gibt), aber das bedeutet nicht, dass es funktioniert auf jedem PC genauso.

Der übliche Trick hier ist die Verwendung von "epsilon" beim Runden. Wie (int)(Math.log(x)/Math.log(2)+1e-10)sollte niemals scheitern. Die Wahl dieses "Epsilons" ist keine triviale Aufgabe.

Mehr Demonstration mit einer allgemeineren Aufgabe - versuchen zu implementieren int log(int x, int base):

Der Testcode:

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

Wenn wir die einfachste Implementierung des Logarithmus verwenden,

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

dies druckt:

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

Um Fehler vollständig zu beseitigen, musste ich epsilon hinzufügen, das zwischen 1e-11 und 1e-14 liegt. Könnten Sie dies vor dem Testen gesagt haben? Ich konnte es definitiv nicht.

Rotsor
quelle
3
"Es bedeutet nicht, dass es auf jedem PC genauso funktioniert" - Wenn Sie es verwenden würden strictfp, nein?
Ken
@ Ken: Vielleicht ... Aber Sie können nur sicher sein, wenn Sie alle möglichen Eingabewerte vollständig aufgelistet haben. (Wir haben Glück, dass es hier so wenige gibt)
Rotsor
2
Technisch gesehen ja, aber das gilt für jede Funktion. Irgendwann müssen Sie darauf vertrauen, dass Ihr Programm gut genug funktioniert, wenn Sie die verfügbare Dokumentation verwenden und einen ausgewählten, aber verschwindend kleinen Teil "aller möglichen Eingabewerte" testen. strictfpscheint tatsächlich viel Mist bekommen zu haben, weil er tatsächlich streng ist. :-)
Ken
Wie wäre return ((long)Math.log(x) / (long)Math.log(base));es, alle Fehler zu lösen?
Kein Fehler
92

Dies ist die Funktion, die ich für diese Berechnung verwende:

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

Es ist etwas schneller als Integer.numberOfLeadingZeros () (20-30%) und fast zehnmal schneller (jdk 1.6 x64) als eine auf Math.log () basierende Implementierung wie diese:

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

Beide Funktionen geben für alle möglichen Eingabewerte die gleichen Ergebnisse zurück.

Update: Der Java 1.7-Server JIT kann einige statische mathematische Funktionen durch alternative Implementierungen ersetzen, die auf den CPU-Eigenschaften basieren. Eine dieser Funktionen ist Integer.numberOfLeadingZeros (). Bei einer Server-VM ab 1.7 ist eine Implementierung wie die fragliche tatsächlich etwas schneller als die binlogoben genannte. Leider scheint die Client-JIT diese Optimierung nicht zu haben.

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

Diese Implementierung liefert auch die gleichen Ergebnisse für alle 2 ^ 32 möglichen Eingabewerte wie die beiden anderen Implementierungen, die ich oben veröffentlicht habe.

Hier sind die tatsächlichen Laufzeiten auf meinem PC (Sandy Bridge i7):

JDK 1.7 32-Bit-Client-VM:

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

JDK 1.7 x64-Server-VM:

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

Dies ist der Testcode:

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
quelle
9
Die BSRAnweisung von x86 funktioniert 32 - numberOfLeadingZeros, ist jedoch für 0 undefiniert. Daher muss ein (JIT) -Compiler auf Nicht-Null prüfen, wenn er nicht beweisen kann, dass dies nicht erforderlich ist. Die BMI-Befehlssatzerweiterungen (Haswell und neuer) wurden eingeführt und in einem einzigen Befehl LZCNTvollständig implementiert numberOfLeadingZeros. Sie sind beide 3-Zyklus-Latenz, 1 pro Zyklus-Durchsatz. Daher würde ich die Verwendung unbedingt empfehlen numberOfLeadingZeros, da dies eine gute JVM erleichtert. (Das einzig Seltsame lzcntist, dass es eine falsche Abhängigkeit vom alten Wert des Registers hat, das es überschreibt.)
Peter Cordes
Ich bin am meisten an Ihrem Kommentar zu Java 1.7 Server JIT CPU Intrinsics-Ersetzungen interessiert. Haben Sie eine Referenz-URL? (JIT Quellcode Link ist auch OK.)
Kevinarpe
37

Versuchen Math.log(x) / Math.log(2)

Chris B.
quelle
8
Obwohl dies mathematisch korrekt ist, beachten Sie bitte, dass die Gefahr einer Fehlberechnung aufgrund ungenauer Gleitkomma-Arithmetik besteht, wie in Rotsors Antwort erläutert.
Leeyuiwah
28

Sie können die Identität verwenden

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

Dies würde also für log2 gelten.

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

Stecken Sie dies einfach in die Java Math Log10-Methode ....

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

hvgotcodes
quelle
3
Obwohl dies mathematisch korrekt ist, beachten Sie bitte, dass die Gefahr einer Fehlberechnung aufgrund ungenauer Gleitkomma-Arithmetik besteht, wie in Rotsors Antwort erläutert.
Leeyuiwah
18

Warum nicht:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}
TofuBeer
quelle
6
Obwohl dies mathematisch korrekt ist, beachten Sie bitte, dass die Gefahr einer Fehlberechnung aufgrund ungenauer Gleitkomma-Arithmetik besteht, wie in Rotsors Antwort erläutert.
Leeyuiwah
9

Es gibt die Funktion in Guavenbibliotheken:

LongMath.log2()

Also schlage ich vor, es zu benutzen.

Demetr
quelle
Wie kann ich dieses Paket zu meiner Anwendung hinzufügen?
Elvin Mammadov
Laden Sie das Glas von hier herunter und fügen Sie es dem Erstellungspfad Ihres Projekts hinzu.
Debosmit Ray
2
Sollte ich meiner Anwendung eine Bibliothek hinzufügen, um nur eine Funktion zu verwenden?
Tash Pemhiwa
7
Warum genau würden Sie vorschlagen, es zu verwenden? Ein kurzer Blick auf die Guava-Quelle zeigt, dass sie dasselbe tut wie die OP-Methode (einige sehr klar verstandene Codezeilen), auf Kosten des Hinzufügens einer ansonsten nutzlosen Abhängigkeit. Nur weil Google etwas anbietet, ist es nicht besser, als das Problem und die Lösung selbst zu verstehen.
Dave
3

Diese Funktion gibt die Obergrenze des Binärprotokolls einer Zahl zurück, um die x4u-Antwort zu ergänzen, die den Boden des Binärprotokolls einer Zahl angibt:

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
quelle
Wo ist die Variable "number"?
Barteks2x
3

Einige Fälle haben gerade funktioniert, als ich Math.log10 verwendet habe:

public static double log2(int n)
{
    return (Math.log10(n) / Math.log10(2));
}
Yachthafen
quelle
0

Fügen wir hinzu:

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

Quelle: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

Guido Celada
quelle
Das würde eine Nachschlagetabelle erstellen. Das OP forderte einen schnelleren Weg, um einen Logarithmus zu "berechnen".
Dave
-3

Zur Berechnung der logarithmischen Basis 2 von n kann folgender Ausdruck verwendet werden:

double res = log10(n)/log10(2);
Akanksha
quelle
2
Diese Antwort wurde bereits mehrmals veröffentlicht und es wurde bereits festgestellt, dass sie aufgrund eines Rundungsfehlers möglicherweise ungenau ist. Beachten Sie das OP, das nach dem Integralwert gefragt wird. Es ist überhaupt nicht klar, welche Rundungsgenauigkeit verwendet werden muss, um von hier zu einer ganzen Zahl zu gelangen.
AnotherParker