Comment calculez-vous la base de journal 2 en Java pour les entiers?

Question

J'ai utiliser la fonction suivante pour calculer le logarithme de base 2 pour les entiers:

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

A-t-elle des performances optimales?

Quelqu'un sait-prêt J2SE la fonction de l'API pour cette raison?

UPD1 Surprise pour moi, float point de l'arithmétique semble être plus rapide que l'entier de l'arithmétique.

UPD2 en Raison de commentaires je vais mener l'enquête plus détaillée.

UPD3 Mon arithmétique des nombres entiers fonction est 10 fois plus rapide que les Mathématiques.log(n)/Math.log(2).

Answer 1

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 Entier.numberOfLeadingZeros() (20-30%) et près de 10 fois plus rapide (jdk 1.6 x64) de Mathématiques.log() en fonction de la mise en œuvre 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: La Java 1.7 serveur JIT est capable de remplacer un peu statique de fonctions mathématiques avec les autres implémentations basées sur le CPU intrinsèques. L'une de ces fonctions est de type Entier.numberOfLeadingZeros(). Donc, avec un 1.7 ou plus récent server VM, une œuvre comme celle de la question est en fait légèrement plus rapide que l' binlog - 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 œuvre renvoie les mêmes résultats pour tous les 2^32 valeurs d'entrée possibles comme les deux autres implémentations que j'ai posté ci-dessus.

Ici sont les véritables moteurs d'exécution sur mon PC (Sandy Bridge i7):

JDK 1.7 32 Bits 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

C'est 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 );

Answer 2

Si vous êtes à la réflexion sur l'utilisation de la virgule flottante pour les aider avec entier arithmétique, vous devez être prudent.

J'ai l'habitude d'essayer d'éviter FP calculs à chaque fois que possible.

Les opérations à virgule flottante ne sont pas exactes. Vous ne pouvez jamais savoir avec certitude ce que sera (int)(Math.log(65536)/Math.log(2)) évaluer. Par exemple, Math.ceil(Math.log(1<<29) / Math.log(2)) 30 sur mon PC où mathématiquement cela devrait être exactement 29. Je n'ai pas trouver une valeur de x, où (int)(Math.log(x)/Math.log(2)) d'échec (juste parce qu'il y a seulement 32 "dangereux" valeurs), mais cela ne signifie pas que cela fonctionnera de la même manière sur n'importe quel PC.

L'habitude astuce ici est d'utiliser "epsilon" lors de l'arrondissement. Comme (int)(Math.log(x)/Math.log(2)+1e-10) ne doit jamais échouer. Le choix de cette "epsilon" n'est pas une tâche triviale.

Plus de démonstration, à l'aide d'une tâche plus générale - essayer de mettre en oeuvre 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 la plus directe de mise en œuvre de logarithme,

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

cette affiche:

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 complètement se débarrasser des erreurs, j'ai dû ajouter epsilon qui est entre 1e-11 1e-14. Pourriez-vous lui avez dit cela avant de tester? J'ai vraiment pas pu.

Answer 3

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

Answer 4

vous pouvez utiliser l'identité

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

donc cela serait applicable pour log2.

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

Il suffit de le brancher à la méthode java Math Log10 ....

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

Answer 5

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

C'est la manière habituelle acceptée. Il n'y a pas de fonction intégrée pour log2, mais en créer une est trivial et donnera une meilleure cohésion à votre code.

(si vous vous rappelez du cours de mathématiques, log10 x = ln x / ln 10 ): D