java.math.BigInteger pow (exponente) pregunta

Question

Hice algunas pruebas en el método de pow (exponente). Desafortunadamente, mis habilidades matemáticas no son lo suficientemente fuertes como para manejar el siguiente problema.

Estoy usando este código:

BigInteger.valueOf(2).pow(var); 

Resultados:

• var | hora en ms
• 2000000 |
• 2500000 |
• 3000000 | 22379
• 3500000 | 32147
• 4000000 |
• 4500000 |
• 5000000 | 49922

Ver? 2,500,000 de exponente se calcula casi tan rápido como 2,000,000. 4,500,000 se calcula mucho más rápido que 4,000,000.

¿Por qué es eso?

Para darle un poco de ayuda, aquí está la implementación original de BigInteger.pow (exponente):

public BigInteger pow(int exponent) { 
    if (exponent < 0) 
     throw new ArithmeticException("Negative exponent"); 
    if (signum==0) 
     return (exponent==0 ? ONE : this); 

    // Perform exponentiation using repeated squaring trick 
     int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 
    int[] baseToPow2 = this.mag; 
     int[] result = {1}; 

    while (exponent != 0) { 
     if ((exponent & 1)==1) { 
     result = multiplyToLen(result, result.length, 
             baseToPow2, baseToPow2.length, null); 
     result = trustedStripLeadingZeroInts(result); 
     } 
     if ((exponent >>>= 1) != 0) { 
       baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); 
     baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); 
     } 
    } 
    return new BigInteger(result, newSign); 
    } 

Answer 1

El algoritmo utiliza escuadrado repetido (squareToLen) y multiplicación (multiplyToLen).El tiempo de ejecución de estas operaciones depende del tamaño de los números involucrados. Las multiplicaciones de los números grandes cerca del final del cálculo son mucho más costosas que las del inicio.

La multiplicación solo se realiza cuando esta condición es verdadera: ((exponent & 1)==1). El número de operaciones cuadradas depende del número de bits en el número (sin incluir los ceros a la izquierda), pero solo se requiere una multiplicación para los bits que están configurados en 1. Es más fácil ver las operaciones que se requieren al observar el binario representación del número:

 
2000000: 0000111101000010010000000 
2500000: 0001001100010010110100000 
3000000: 0001011011100011011000000 
3500000: 0001101010110011111100000 
4000000: 0001111010000100100000000 
4500000: 0010001001010101000100000 
5000000: 0010011000100101101000000 

Tenga en cuenta que 2,5 M y 4,5 M son afortunados en que tienen menos bits altos establecidos que los números que les rodean. La próxima vez que esto sucede es por lo 8.5M:

 
8000000: 0011110100001001000000000 
8500000: 0100000011011001100100000 
9000000: 0100010010101010001000000 

Los puntos clave son potencias exactas de 2.

 
1048575: 0001111111111111111111111 // 16408 ms 
1048576: 0010000000000000000000000 // 6209 ms 

Answer 2

Sólo una conjetura:

el exponente se maneja poco a poco, y si el menos significativo bit es 1 trabajo adicional hecho.

Si L es el número de bits en el exponente y A el número de bits que son 1 y t1 el tiempo para procesar la parte común y t2 el tiempo de procesamiento adicional cuando el bit menos significativo es 1

entonces el tiempo de ejecución sería

L t1 + a t2

o el tiempo es dependiente del número de 1 de en la representación binaria.

ahora escribir un pequeño programa para verificar mi teoría ...

Answer 3

no estoy seguro de cuántas veces se le han acabado los tiempos de su. Como algunos de los comentaristas han señalado, es necesario programar las operaciones muchas, muchas veces para obtener buenos resultados (y aún así pueden estar equivocados).

Suponiendo que ha cronometrado bien las cosas, recuerde que hay muchos atajos que se pueden tomar en matemáticas. No tiene que hacer las operaciones 5 * 5 * 5 * 5 * 5 * 5 para calcular 5^6.

Aquí hay una forma de hacerlo mucho más rápido. http://en.wikipedia.org/wiki/Exponentiation_by_squaring