java performance discrete-mathematics logarithm

¿Cómo se calcula log base 2 en Java para enteros?



performance discrete-mathematics (8)

Utilizo la siguiente función para calcular la base de registro 2 para enteros:

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

¿Tiene un rendimiento óptimo?

¿Alguien sabe la función lista API J2SE para ese propósito?

UPD1 Sorprendentemente para mí, la aritmética de punto flotante parece ser más rápida que la aritmética entera.

UPD2 Debido a los comentarios realizaré una investigación más detallada.

UPD3 Mi función aritmética entera es 10 veces más rápida que Math.log (n) /Math.log (2).

Está la función en las bibliotecas de guayabas:

LongMath.log2()

Entonces sugiero usarlo.

Esta es la función que uso para este cálculo:

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 ligeramente más rápido que Integer.numberOfLeadingZeros () (20-30%) y casi 10 veces más rápido (jdk 1.6 x64) que una implementación basada en Math.log () como esta:

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

Ambas funciones devuelven los mismos resultados para todos los posibles valores de entrada.

Actualización: El JIT del servidor Java 1.7 puede reemplazar algunas funciones matemáticas estáticas con implementaciones alternativas basadas en intrínsecos de la CPU. Una de esas funciones es Integer.numberOfLeadingZeros (). Entonces, con una máquina virtual de servidor 1.7 o posterior, una implementación como la de la pregunta es en realidad un poco más rápida que el binlog anterior. Desafortunadamente, el cliente JIT no parece tener esta optimización.

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

Esta implementación también devuelve los mismos resultados para todos los 2 ^ 32 posibles valores de entrada que las otras dos implementaciones que publiqué anteriormente.

Aquí están los tiempos de ejecución reales en mi PC (Sandy Bridge i7):

JDK 1.7 32 Bits cliente VM:

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

Servidor JDK 1.7 x64 VM:

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

Este es el código de prueba:

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

Para agregar a x4u la respuesta, que le da el piso del registro binario de un número, esta función devuelve el tope del registro binario de un número:

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

Por qué no:

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

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

Si está pensando en utilizar el punto flotante para ayudar con la aritmética entera, debe tener cuidado.

Por lo general, trato de evitar los cálculos FP siempre que sea posible.

Las operaciones de coma flotante no son exactas. Nunca se puede saber con certeza qué va a (int)(Math.log(65536)/Math.log(2)) evaluar. Por ejemplo, Math.ceil(Math.log(1<<29) / Math.log(2)) es 30 en mi PC donde matemáticamente debería ser exactamente 29. No encontré un valor para x donde (int)(Math.log(x)/Math.log(2)) falla (solo porque solo hay 32 valores "peligrosos"), pero eso no significa que funcione de la misma manera en cualquier PC.

El truco habitual aquí es usar "epsilon" al redondear. Like (int)(Math.log(x)/Math.log(2)+1e-10) nunca debe fallar. La elección de este "épsilon" no es una tarea trivial.

Más demostración, usando una tarea más general: tratando de implementar int log(int x, int base) :

El código de prueba:

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 usamos la implementación más directa del logaritmo,

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

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

Para deshacerse completamente de los errores, tuve que agregar épsilon, que está entre 1e-11 y 1e-14. ¿Podrías haber dicho esto antes de las pruebas? Definitivamente no podría.

agreguemos:

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

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