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

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

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

At-il une performance optimale?

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

UPD1 Étonnamment pour moi, l’arithmétique des points flottants semble être plus rapide que l’arithmétique entière.

UPD2 Suite à des commentaires, je mènerai une enquête plus détaillée.

UPD3 Ma fonction arithmétique sur les entiers est 10 fois plus rapide que Math.log (n) /Math.log (2).

Si vous envisagez d’utiliser des virgules flottantes pour vous aider avec l’arithmétique des nombres entiers, vous devez faire attention.

J’essaie généralement d’éviter les calculs de PF chaque fois que possible.

Les opérations en virgule flottante ne sont pas exactes. Vous ne pouvez jamais savoir avec certitude à quoi servira (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 de la même manière sur n'importe quel PC.

L'astuce habituelle consiste à utiliser "epsilon" lors de l'arrondissement. Like (int)(Math.log(x)/Math.log(2)+1e-10) ne doit jamais échouer. Le choix de ce "epsilon" n'est pas une tâche sortingviale.

Plus de démonstration, en utilisant une tâche plus générale - en essayant d'implémenter 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 éliminer complètement les erreurs, j'ai dû append epsilon qui se situe entre 1e-11 et 1e-14. Auriez-vous pu le dire avant de tester? Je ne pouvais 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 Java 1.7 JIT est capable de remplacer quelques fonctions mathématiques statiques par des implémentations alternatives basées sur des éléments insortingnsèques du processeur. Une de ces fonctions est Integer.numberOfLeadingZeros (). Donc, avec un serveur virtuel de 1,7 ou plus récent, une implémentation comme celle de la question est en fait légèrement plus rapide que le binlog ci-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 

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

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

vous pouvez utiliser l’identité

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

donc ce serait applicable pour log2.

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

il suffit de twigr cette méthode 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 goyave:

 LongMath.log2() 

Je suggère donc de l’utiliser.

Pour append une réponse à x4u, ce qui vous donne le plancher du journal binary d’un nombre, cette fonction renvoie le plafond du journal binary 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); } 

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 log 2 de n, l’expression suivante peut être utilisée:

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