Calcolo di potenze estremamente grandi di 2

Question

Ho realizzato un programma in Java che calcola le potenze di due, ma sembra molto inefficiente. Per potenze più piccole (2^4000, diciamo), lo fa in meno di un secondo. Tuttavia, sto cercando di calcolare 2^43112609, che è maggiore del numero primo noto più grande. Con oltre 12 milioni di cifre, ci vorrà molto tempo per essere eseguito. Ecco il mio codice finora:

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

Questo non è per un progetto scolastico o altro; solo per il gusto di farlo. Sarebbe gradito qualsiasi aiuto su come rendere questo più efficiente! Grazie!

Kyle

P.S. Ho omesso di menzionare che l'output dovrebbe essere in base 10, non in binario.

Answer 1

La chiave qui è da notare che:

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) 

Poi dal:

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

è possibile trovare il restante (2^9558177) utilizzando lo stesso metodo, e dal momento che (2^9558177 = 2^8388608 * 2^1169569), è possibile trovare 2^1169569 utilizzando il stesso metodo, e dal (2^1169569 = 2^1048576 * 2^120993), è possibile trovare 2^120993 utilizzando lo stesso metodo, e così via ...

EDIT: in precedenza c'è stato un errore in questa sezione, ora è fissato:

Inoltre, un'ulteriore semplificazione e l'ottimizzazione notando che:

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

Si noti inoltre che 2^(0*n) = 2^0 = 1

Utilizzando questo algoritmo, è possibile calcolare la tabella di 2^1, 2^2, 2^4, 2^8, 2^16 ... 2^33554432 in 25 moltiplicazioni. Quindi è possibile convertire 43112609 nella sua rappresentazione binaria e trovare facilmente 2^43112609 utilizzando meno di 25 moltiplicazioni. In totale, è necessario utilizzare meno di 50 moltiplicazioni di trovare qualsiasi 2^n dove n è compreso tra 0 e 67108864.

Answer 2

Visualizzarlo in binario è facile e veloce, il più rapidamente possibile scrivere sul disco! 100000 ......: D

Answer 3

Come accennato, le potenze di due corrispondono a cifre binarie. Il binario è base 2, quindi ogni cifra è il doppio del valore del precedente.

Ad esempio:

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

binario è base 2 (è per questo che si chiama "base 2", 2 è la base degli esponenti), in modo che ogni cifra è il doppio del valore di quello precedente. L'operatore di spostamento ('< <' nella maggior parte delle lingue) viene utilizzato per spostare ogni cifra binaria a sinistra, ogni turno è equivalente a moltiplicare per due.

Ad esempio:

1 << 6 = 2^6 = 64 

Essendo una semplice operazione ad binaria, molti processori possono fare questo in modo estremamente rapido per i numeri che possono adattarsi in un registro (8 - 64 bit, a seconda del processore). Farlo con numeri più grandi richiede un qualche tipo di astrazione (ad esempio Bignum), ma dovrebbe comunque essere un'operazione estremamente rapida. Tuttavia, farlo a 43112609 bit richiederà un po 'di lavoro.

Per darvi un piccolo contesto, 2 < < 4311260 (manca l'ultima cifra) è lunga 1297181 cifre. Assicurati di avere abbastanza RAM per gestire il numero di uscita, se il tuo computer non si scambierà il disco, il che paralizzerà la tua velocità di esecuzione.

Poiché il programma è così semplice, considerare anche il passaggio a un linguaggio che compila direttamente in assemblaggio, ad esempio C.

In verità, generando il valore è banale (sappiamo già la risposta, uno seguita da 43112609 zeri). Ci vorrà un bel po 'di tempo per convertirlo in decimale.

Answer 4

Come suggerisce @John SMith, puoi provare. 2^4000

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

EDIT: Trasformare un binario in un decimale è (n^2) problema O. Quando raddoppi il numero di bit raddoppi la lunghezza di ogni operazione e raddoppi il numero di cifre prodotte.

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

NOTA: Il tempo impiegato è entriely nel toString(), non lo shiftLeft che prende < 1 ms, anche per 10 milioni.

Answer 5

L'altra chiave da notare è che la CPU è molto più veloce a moltiplicare interi e anela di te facendo lunga moltiplicazione in Java. Ottieni quel numero diviso in pezzi lunghi (64 byte), e moltiplica e trasporta i blocchi invece delle singole cifre. Accoppiato con la risposta precedente (usando la quadratura invece della moltiplicazione sequenziale di 2) probabilmente lo accelererà di un fattore di 100x o più.

Modifica

ho tentato di scrivere un metodo di suddivisione in blocchi e squadratura e funziona un po 'più lento rispetto BigInteger (13,5 secondi vs 11,5 secondi per calcolare 2^524288). Dopo aver fatto alcuni tempi ed esperimenti, il metodo più veloce sembra essere ripetuto quadratura con la classe BigInteger:

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

• Alcuni risultati sincronizzazione per il potere di 2 esponenti (2^(2^n) per qualche n)
• 131.072-0,83 secondi
• 262144 - 3.02 secondi
• 524.288-11,75 secondi
• 1048576 - 49.66 secondi

A questo ritmo di crescita, ci vorranno circa 77 ore per calcolare 2^33554432, per non parlare del tempo che memorizza e aggiunge tutti i poteri insieme per ottenere il risultato finale di 2^43112609.

Edit 2

In realtà, per davvero grandi esponenti, il metodo BigInteger.ShiftLeft è il più veloce.Stimo che per 2^33554432 con ShiftLeft ci vorranno circa 28-30 ore. Chiedo quanto velocemente una versione Assemblea C o avrebbero preso ...

Answer 6

Sia n = 43112609.

Assunzione: Si desidera stampare 2^n in decimali.

Mentre riempire un vettore bit che rappresenta 2^n in binario è banale, la conversione di quel numero in notazione decimale richiederà un po 'di tempo. Ad esempio, l'implementazione di java.math.BigInteger.toString richiede operazioni O (n^2). E questo è probabilmente il motivo per

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

ancora non è terminato dopo un'ora di tempo di esecuzione ...

Cominciamo con un'analisi asintotica del vostro algoritmo. Il tuo ciclo esterno verrà eseguito n volte. Per ogni iterazione, farai un'altra operazione O (n^2). Cioè, il tuo algoritmo è O (n^3), quindi è prevista una scarsa scalabilità.

È possibile ridurre questo a O (n^2 log n) facendo uso di

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

(che richiede solo 8 moltiplicazioni) anziché 64 moltiplicazioni di

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

(La generalizzazione di esponenti arbitrari è lasciata come esercizio per te. ite l'esponente come numero binario - o guarda la risposta di Lie Ryan).

Per velocizzare la moltiplicazione, è possibile utilizzare Karatsuba Algorithm, riducendo il tempo di esecuzione complessivo a O (n^((log 3)/(log 2)) log n).

Answer 7

Perché in realtà si vogliono tutte le cifre del risultato (a differenza, ad esempio, RSA, dove si è interessati solo al residuo mod un numero che è molto più piccolo dei numeri che abbiamo qui), penso che l'approccio migliore sia probabilmente quello di estrarre nove cifre decimali contemporaneamente usando la divisione lunga implementata usando la moltiplicazione. Iniziamo con residuo pari a zero, e applicare la seguente per ogni 32 bit a sua volta (MSB prima)

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

quindi memorizzare il risultato nei 32 bit appena letto, e ciclicamente ogni parola inferiore. Il residuo dopo l'ultimo passaggio saranno le nove cifre decimali inferiori del risultato. Dal momento che il calcolo di una potenza di due in binario sarà veloce e facile, penso che dividere per convertire in decimale potrebbe essere l'approccio migliore.

BTW, questo calcola 2^640000 in circa 15 secondi in vb.net, quindi 2^43112609 dovrebbe essere di circa cinque ore per calcolare tutte le 12.978.188 cifre.