Cálculo de potencias extremadamente grandes de 2

Question

He hecho un programa en Java que calcula potencias de dos, pero parece muy ineficiente. Para poderes más pequeños (2^4000, por ejemplo), lo hace en menos de un segundo. Sin embargo, estoy buscando calcular 2^43112609, que es uno mayor que el número primo conocido más grande. Con más de 12 millones de dígitos, tomará mucho tiempo ejecutarlo. Aquí está mi código hasta ahora:

import java.io.*; 

public class Power 
{ 
private static byte x = 2; 
private static int y = 43112609; 
private static byte[] a = {x}; 
private static byte[] b = {1}; 
private static byte[] product; 
private static int size = 2; 
private static int prev = 1; 
private static int count = 0; 
private static int delay = 0; 
public static void main(String[] args) throws IOException 
{ 
    File f = new File("number.txt"); 
    FileOutputStream output = new FileOutputStream(f); 
    for (int z = 0; z < y; z++) 
    { 
    product = new byte[size]; 
    for (int i = 0; i < a.length; i++) 
    { 
    for (int j = 0; j < b.length; j++) 
    { 
    product[i+j] += (byte) (a[i] * b[j]); 
    checkPlaceValue(i + j); 
    } 
    } 
    b = product; 
    for (int i = product.length - 1; i > product.length - 2; i--) 
    { 
    if (product[i] != 0) 
    { 
    size++; 
    if (delay >= 500) 
    { 
     delay = 0; 
     System.out.print("."); 
    } 
    delay++; 
    } 
    } 
    } 
    String str = ""; 
    for (int i = (product[product.length-1] == 0) ? 
    product.length - 2 : product.length - 1; i >= 0; i--) 
    { 
    System.out.print(product[i]); 
    str += product[i]; 
    } 
    output.write(str.getBytes()); 
    output.flush(); 
    output.close(); 
    System.out.println(); 
} 

public static void checkPlaceValue(int placeValue) 
{ 
    if (product[placeValue] > 9) 
    { 
    byte remainder = (byte) (product[placeValue]/10); 
    product[placeValue] -= 10 * remainder; 
    product[placeValue + 1] += remainder; 
    checkPlaceValue(placeValue + 1); 
    } 
} 
} 

Esto no es para un proyecto escolar ni nada; solo por diversión. Cualquier ayuda en cuanto a cómo hacer que esto sea más eficiente sería apreciada. ¡Gracias!

Kyle

P.S. No mencioné que la salida debería estar en base-10, no en binario.

Answer 1

La clave aquí es darse cuenta de que:

2^2 = 4 
2^4 = (2^2)*(2^2) 
2^8 = (2^4)*(2^4) 
2^16 = (2^8)*(2^8) 
2^32 = (2^16)*(2^16) 
2^64 = (2^32)*(2^32) 
2^128 = (2^64)*(2^64) 
... and in total of 25 steps ... 
2^33554432 = (2^16777216)*(16777216) 

Entonces desde:

2^43112609 = (2^33554432) * (2^9558177) 

se encuentra la (2^9558177) restante usando el mismo método, y desde (2^9558177 = 2^8388608 * 2^1169569), usted puede encontrar 2^1169569 utilizando el mismo método, y desde (2^1169569 = 2^1048576 * 2^120993), puede encontrar 2^120993 utilizando el mismo método, y así sucesivamente ...

EDIT: previamente había un error en esta sección, ahora es fijo:

Además, una mayor simplificación y optimización observando que:

2^43112609 = 2^(0b10100100011101100010100001) 
2^43112609 = 
     (2^(1*33554432)) 
    * (2^(0*16777216)) 
    * (2^(1*8388608)) 
    * (2^(0*4194304)) 
    * (2^(0*2097152)) 
    * (2^(1*1048576)) 
    * (2^(0*524288)) 
    * (2^(0*262144)) 
    * (2^(0*131072)) 
    * (2^(1*65536)) 
    * (2^(1*32768)) 
    * (2^(1*16384)) 
    * (2^(0*8192)) 
    * (2^(1*4096)) 
    * (2^(1*2048)) 
    * (2^(0*1024)) 
    * (2^(0*512)) 
    * (2^(0*256)) 
    * (2^(1*128)) 
    * (2^(0*64)) 
    * (2^(1*32)) 
    * (2^(0*16)) 
    * (2^(0*8)) 
    * (2^(0*4)) 
    * (2^(0*2)) 
    * (2^(1*1)) 

También tenga en cuenta que 2^(0*n) = 2^0 = 1

Uso este algoritmo, puede calcular la tabla de 2^1, 2^2, 2^4, 2^8, 2^16 ... 2^33554432 en 25 multiplicaciones. Luego puede convertir 43112609 en su representación binaria y encontrar fácilmente 2^43112609 usando menos de 25 multiplicaciones. En total, debe usar menos de 50 multiplicaciones para encontrar 2^n donde n se encuentre entre 0 y 67108864.

Answer 2

Mostrarlo en formato binario es fácil y rápido, ¡tan rápido como pueda escribir en el disco! 100000 ......: D

Answer 3

Como se mencionó, las potencias de dos corresponden a dígitos binarios. Binary es la base 2, por lo que cada dígito es el doble del valor de la anterior.

Por ejemplo:

1 = 2^0 = b1 
    2 = 2^1 = b10 
    4 = 2^2 = b100 
    8 = 2^3 = b1000 
    ... 

binario es base 2 (que es por qué se llama "base 2", 2 es el de la base de los exponentes), por lo que cada dígito es el doble del valor de la anterior. El operador de desplazamiento ('< <' en la mayoría de los idiomas) se usa para desplazar cada dígito binario a la izquierda, siendo cada turno equivalente a un multiplicador por dos.

Por ejemplo:

1 << 6 = 2^6 = 64 

Ser una simple operación de tal binario, la mayoría de los procesadores pueden hacer esto de forma extremadamente rápida para los números que pueden caber en un registro (8 - 64 bits, dependiendo del procesador). Hacerlo con números más grandes requiere algún tipo de abstracción (Bignum, por ejemplo), pero aún así debería ser una operación extremadamente rápida. Sin embargo, hacerlo a 43112609 bits requerirá un poco de trabajo.

Para darle un pequeño contexto, 2 < < 4311260 (falta el último dígito) tiene 1297181 dígitos de longitud. Asegúrese de tener suficiente memoria RAM para manejar el número de salida, si no lo hace, su computadora se intercambiará en el disco, lo que perjudicará su velocidad de ejecución.

Desde que el programa es tan simple, también considerar el cambio a un lenguaje que compila directamente en el montaje, tal como C.

En verdad, lo que genera el valor es trivial (que ya sabemos la respuesta, un uno seguido de 43112609 ceros). Tardará bastante más tiempo convertirlo en decimal.

Answer 4

Como sugiere @John SMith, puedes intentarlo. 2^4000

System.out.println(new BigInteger("1").shiftLeft(4000)); 

EDITAR: Convertir un binario en un decimal es un problema O (n^2). Cuando duplica el número de bits, dobla la longitud de cada operación y duplica la cantidad de dígitos producidos.

2^100,000 takes 0.166 s 
2^1000,000 takes 11.7 s 
2^10,000,000 should take 1200 seconds. 

NOTA: El tiempo necesario es entriely en el toString(), no el shiftLeft que tiene < 1 ms, incluso para los 10 millones.

Answer 5

La otra clave que debe tener en cuenta es que su CPU es mucho más rápida al multiplicar ints y longs que usted haciendo long multiplicación en Java. Haz que el número se divida en fragmentos largos (64 bytes) y multiplica y transporta los fragmentos en lugar de dígitos individuales. Junto con la respuesta anterior (usando cuadratura en lugar de multiplicación secuencial de 2) probablemente la acelerará por un factor de 100x o más.

Editar

he tratado de escribir un método CHUNKING y elevar al cuadrado y se ejecuta ligeramente más lento que BigInteger (13,5 vs 11,5 segundos segundos para calcular 2^524288). Después de hacer algunos tiempos y experimentos, el método más rápido parece ser repetido cuadratura con la clase BigInteger:

public static String pow3(int n) { 
    BigInteger bigint = new BigInteger("2"); 
    while (n > 1) { 
     bigint = bigint.pow(2); 
     n /= 2; 
    } 
    return bigint.toString(); 
} 

• Algunos resultados sincronización para la energía de 2 exponentes (2^(2^n) para algún n)
• 131,072 mil - 0,83 segundos
• 262144 - 3.02 segundos
• 524288 - 11,75 segundos
• 1048576 - 49.66 segundos

A esta tasa de crecimiento, tomaría aproximadamente 77 horas calcular 2^33554432, y mucho menos el tiempo de almacenamiento y la suma de todas las potencias para obtener el resultado final de 2^43112609.

Editar 2

En realidad, por muy grandes exponentes, el método BigInteger.ShiftLeft es el más rápido.Estimo que para 2^33554432 con ShiftLeft, tomaría aproximadamente 28-30 horas. Pregunto qué tan rápido tomarían una C o versión Asamblea ...

Answer 6

Sea n = 43112609.

Supuesto: Usted desea imprimir 2^n en decimal.

Si bien llenar un vector de bits que representa 2^n en binario es trivial, la conversión de ese número a notación decimal tomará un tiempo. Por ejemplo, la implementación de java.math.BigInteger.toString toma O (n^2) operaciones. Y eso es probablemente la razón por

BigInteger.ONE.shiftLeft(43112609).toString() 

todavía no ha terminado después de una hora de tiempo de ejecución ...

Vamos a empezar con un análisis asintótico de su algoritmo. Su bucle externo se ejecutará n veces. Para cada iteración, realizará otras operaciones O (n^2). Es decir, su algoritmo es O (n^3), por lo que se espera una escabilidad pobre.

Puede reducir este a O (n^2 log n) haciendo uso de

x^64 = x^(2 * 2 * 2 * 2 * 2 * 2) = ((((((x^2)^2)^2)^2)^2)^2

(que requiere sólo 8 multiplicaciones) en lugar de los 64 multiplicaciones de

x^64 = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x

(Generalizar a exponentes arbitrarios se deja como ejercicio para usted. Sugerencia: Wr ite el exponente como número binario o mire la respuesta de Lie Ryan).

Para acelerar la multiplicación, puede emplear Karatsuba Algorithm, reduciendo el tiempo de ejecución general a O (n^((log 3)/(log 2)) log n).

Answer 7

Porque uno realmente quiere todos los dígitos del resultado (a diferencia, por ejemplo, RSA, donde uno solo está interesado en el mod de residuos un número mucho más pequeño que los números que tenemos aquí) Creo que el mejor enfoque es extraer nueve dígitos decimales a la vez usando la división larga implementada mediante la multiplicación. Comenzar con residuo igual a cero, y aplicar la siguiente para cada uno de 32 bits, a su vez (MSB primero)

 
    residue = (residue SHL 32)+data 
    result = 0 

    temp = (residue >> 30) 
    temp += (temp*316718722) >> 32 
    result += temp; 
    residue -= temp * 1000000000; 

    while (residue >= 1000000000) /* I don't think this loop ever runs more than twice */ 
    { 
    result ++; 
    residue -= 1000000000; 
    } 

a continuación, almacenar el resultado en los 32 bits acaba de leer, y el bucle a través de cada palabra inferior. El residuo después del último paso serán los nueve dígitos decimales inferiores del resultado. Dado que el cálculo de una potencia de dos en binario será rápido y fácil, creo que dividir para convertir a decimal puede ser el mejor enfoque.

Por cierto, esto calcula 2^640000 en aproximadamente 15 segundos en vb.net, por lo que 2^43112609 debe ser de aproximadamente cinco horas para calcular los 12,978,188 dígitos.