Comment calculer la base de journal 2 en Java pour les entiers?

J'utilise la fonction suivante pour calculer le journal de base 2 pour les entiers:

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

At-il des performances optimales?

Est-ce que quelqu'un connaît la fonction API J2SE prête à cet effet?

UPD1 Étonnamment pour moi, l'arithmétique à virgule flottante semble être plus rapide que l'arithmétique entière.

UPD2 En raison des commentaires, je vais mener une enquête plus détaillée.

UPD3 Ma fonction arithmétique entière est 10 fois plus rapide que Math.log (n) /Math.log (2).

Si vous envisagez d'utiliser la virgule flottante pour vous aider avec l'arithmétique entière, vous devez être prudent.

J'essaie généralement d'éviter les calculs de FP autant que possible.

Les opérations en virgule flottante ne sont pas exactes. Vous ne pouvez jamais savoir avec certitude ce qui vaudra (int)(Math.log(65536)/Math.log(2)). Par exemple, Math.ceil(Math.log(1<<29) / Math.log(2))est 30 sur mon PC où mathématiquement il devrait être exactement 29. Je n'ai pas trouvé de valeur pour x où (int)(Math.log(x)/Math.log(2))échoue (simplement parce qu'il n'y a que 32 valeurs "dangereuses"), mais cela ne signifie pas que cela fonctionnera le de la même manière sur n'importe quel PC.

L'astuce habituelle ici est d'utiliser "epsilon" lors de l'arrondi. Comme (int)(Math.log(x)/Math.log(2)+1e-10)ne devrait jamais échouer. Le choix de cet "epsilon" n'est pas une tâche anodine.

Plus de démonstration, en utilisant une tâche plus générale - essayer de mettre en œuvre int log(int x, int base):

Le code de test:

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

Si nous utilisons l'implémentation la plus simple du logarithme,

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

ceci imprime:

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

Pour me débarrasser complètement des erreurs, j'ai dû ajouter epsilon qui se situe entre 1e-11 et 1e-14. Auriez-vous pu le dire avant de tester? Je ne pourrais certainement pas.

C'est la fonction que j'utilise pour ce calcul:

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

Il est légèrement plus rapide que Integer.numberOfLeadingZeros () (20-30%) et presque 10 fois plus rapide (jdk 1.6 x64) qu'une implémentation basée sur Math.log () comme celle-ci:

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

Les deux fonctions renvoient les mêmes résultats pour toutes les valeurs d'entrée possibles.

Mise à jour: Le serveur JIT Java 1.7 est capable de remplacer quelques fonctions mathématiques statiques par des implémentations alternatives basées sur les intrinsèques du processeur. L'une de ces fonctions est Integer.numberOfLeadingZeros (). Ainsi, avec une VM de serveur 1.7 ou plus récente, une implémentation comme celle de la question est en fait légèrement plus rapide que celle binlogci - dessus. Malheureusement, le client JIT ne semble pas avoir cette optimisation.

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

Cette implémentation renvoie également les mêmes résultats pour les 2 ^ 32 valeurs d'entrée possibles que les deux autres implémentations que j'ai publiées ci-dessus.

Voici les temps d'exécution réels sur mon PC (Sandy Bridge i7):

VM client JDK 1.7 32 bits:

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

VM serveur JDK 1.7 x64:

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

Voici le code de test:

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

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

vous pouvez utiliser l'identité

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

ce serait donc applicable pour log2.

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

il suffit de le brancher dans la méthode java Math log10 ....

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

Pourquoi pas:

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

Il y a la fonction dans les bibliothèques de goyaves:

LongMath.log2()

Je suggère donc de l'utiliser.

Pour ajouter à x4u answer, qui vous donne le plancher du log binaire d'un nombre, cette fonction renvoie le ceil du log binaire d'un nombre:

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

Certains cas ont juste fonctionné lorsque j'ai utilisé Math.log10:

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

ajoutons:

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

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

Pour calculer la base logarithmique 2 de n, l'expression suivante peut être utilisée:

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