java.math.BigInteger pow (exponente) pregunta

StackOverflow https://stackoverflow.com/questions/2932869

  •  05-10-2019
  •  | 
  •  

Pregunta

Hice algunas pruebas en pow método (exponente). Por desgracia, 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 | tiempo en ms
  • 2000000 | 11450
  • 2500000 | 12471
  • 3000000 | 22379
  • 3500000 | 32147
  • 4000000 | 46270
  • 4500000 | 31459
  • 5000000 | 49922

Vea? 2.500.000 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);
    }
¿Fue útil?

Solución

Los usos algoritmo repiten cuadratura (squareToLen) y multiplicación (multiplyToLen). El tiempo para estas operaciones a plazo depende del tamaño de los números involucrados. Las multiplicaciones de los grandes números cerca del final del cálculo son mucho más caros que los que están en el inicio.

La multiplicación sólo se realiza cuando se cumple esta condición: ((exponent & 1)==1). El número de operaciones cuadrados depende del número de bits en el número (con exclusión de ceros a la izquierda), pero una multiplicación sólo se requiere para los bits que se establecen a 1. Es más fácil ver las operaciones que se requieren mirando 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

Otros consejos

Sólo una conjetura:

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

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 depende del número de 1 de en la representación binaria.

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

No estoy seguro de cuántas veces se le han acabado los tiempos de su. Como algunos de los comentaristas han señalado, que necesita para operaciones en tiempo muchas, muchas veces para obtener buenos resultados (y que todavía puede ser malo).

Suponiendo que haya cosas cronometrados así, recuerde que hay una gran cantidad de atajos que se pueden tomar en matemáticas. Usted no tiene que hacer las operaciones de 5 * 5 * 5 * 5 * 5 * 5 para calcular 5 ^ 6.

Esta es una manera de hacer que sea mucho más rápido. http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top