¿Cómo se calcula la base de registro 2 en Java para enteros?

Question

que utilizar la siguiente función para calcular log base 2 para los números enteros:

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

¿Cuenta con un rendimiento óptimo?

¿Alguien sabe si la función de la API J2SE lista para tal fin?

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

UPD2Debido a los comentarios que llevarán a cabo una investigación más detallada.

UPD3Mi función aritmética de enteros es 10 veces más rápido que Math.log (n) /Math.log (2).

Answer 1

Si usted está pensando en usar de punto flotante para ayudar con la aritmética de enteros, usted tiene que tener cuidado.

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

Las operaciones de coma flotante no son exactas. Nunca se puede saber con certeza qué evaluará (int)(Math.log(65536)/Math.log(2)). 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 lo hará funciona de la misma manera en cualquier PC.

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

Más manifestación, utilizando una tarea más general - tratar 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 utilizamos la implementación más directo de 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 eliminar completamente los errores, tuve que agregar épsilon, que está entre 1e-11 y 1e-14. ¿Podría haber dicho esto antes de las pruebas? Definitivamente no pude.

Answer 2

Por qué no:

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

Answer 3

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

Answer 4

puede utilizar la identidad

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

lo que esta sería aplicable para log2.

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

sólo tiene que enchufar esto en el método log10 java Matemáticas ....

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

Answer 5

Esta es la función que utilizo 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 Math.log() implementación basada como éste:

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 servidor Java 1.7 JIT es capaz de reemplazar algunas funciones matemáticas estáticas con implementaciones alternativas basadas en intrínsecos de la CPU. Una de esas funciones es Integer.numberOfLeadingZeros(). Por lo tanto, 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 la 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 aplicación también devuelve los mismos resultados para todos los 2^32 posibles valores de entrada como los de los otros dos implementaciones que he publicado anteriormente.

Éstos son 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 

JDK servidor de 1,7 x 64 VM:

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

Este es el código de prueba:

Agregar

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 6

nos dejó:

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

Answer 7

No es la función de las bibliotecas de guayaba:

LongMath.log2() 

por lo que sugiero usarlo.

Answer 8

Para añadir a la respuesta X4U, que le da la baja del registro binario de un número, esta función devuelve el ceil 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); 
}