Capire Algoritmo di Schönhage-Strassen (enormi numeri moltiplicazione)

Question

Ho bisogno di moltiplicare diverse 1000s cifre lunghe interi modo più efficiente possibile in Python. I numeri vengono letti da un file.

Sto cercando di implementare la Schönhage-Strassen algoritmo per intero moltiplicazione, ma mi sono bloccato sulla comprensione la definizione e la matematica dietro di esso, specialmente la fast Fourier Transform.

Qualunque aiutano a comprendere questo algoritmo, come un esempio pratico o qualche pseudo-codice sarebbe molto apprezzato.

Answer 1

Capitolo 4.3.3 di Knuth di TAOCP descrive e ha anche qualche FFT pseudocodice in altri capitoli che potrebbero essere utilizzati per questo.

Answer 2

1000 digit è "piccolo" per Schönhage-Strassen per essere veramente vale la pena utilizzare. Si può avere uno sguardo alla Toom Cook moltiplicazione. gmpy è un wrapper Python per gmp fornire queste funzioni.

Answer 3

Non reinventare la ruota. GMP ha un eccellente implementazione ad alte prestazioni di questo algoritmo e qualsiasi algoritmo scritto in puro Python sarà di almeno 100 volte più lento, semplicemente perché Python è un linguaggio interpretato. Utilizzare gmpy di chiamare GMP dalla vostra applicazione Python. Sono anche curioso quale applicazione si sta lavorando che richiede la moltiplicazione di tali grandi numeri - ci potrebbe essere un modo più semplice per gestire il problema

.

Inoltre, come detto da altre risposte, "lunga diversi 1000s cifre" non è quasi abbastanza a lungo da giustificare Schönhage-Strassen (dovreste avere almeno 10000 cifre decimali, probabilmente più). Alcuni variante Toom-Cook come Toom-3 è normalmente utilizzato in questo intervallo. Anche in questo caso, non scrivere da soli in Python -. Implementazione di GMP è molto attentamente ottimizzato