Comprendere l'algoritmo di Schönhage-Strassen (enorme moltiplicazione di interi)

Ho bisogno di moltiplicare più lunghe interi di 1000 cifre nel modo più efficiente possibile in Python. I numeri sono letti da un file.Comprendere l'algoritmo di Schönhage-Strassen (enorme moltiplicazione di interi)

Sto cercando di implementare l'algoritmo Schönhage-Strassen per la moltiplicazione dell'intero, ma sono bloccato a comprendere la definizione e la matematica dietro di esso, in particolare la trasformata di Fourier veloce.

Qualsiasi aiuto per capire questo algoritmo, come un esempio pratico o qualche pseudo-codice sarebbe molto apprezzato.

fonte

2009-05-14 JPCosta

Un suggerimento molto importante: non tentare di implementare il proprio FFT a meno che non sia necessario. Se è disponibile per Python prova a usare FFTW per il tuo calcolo. Supererà di gran lunga qualsiasi cosa tu possa mai sognare di implementare te stesso. Una semplice FFT non è così difficile, ma la parte difficile è farlo in fretta, soprattutto se i numeri che stai scricchiolando non sono potenze di due. – LiKao

@LiKao: Schönhage-Strassen viene normalmente implementato utilizzando un vettore di dimensioni fisse di numeri interi arbitrari e la Trasformata teoretica numerica, mentre gli FFT implementati da pacchetti come FFTW utilizzano elementi a virgola mobile ea dimensione fissa, quindi non sono in realtà molto utile. –

Il capitolo 4.3.3 di Knuth's TAOCP lo descrive e ha anche qualche pseudocodice FFT in altri capitoli che potrebbero essere utilizzati per questo.

fonte

2009-05-14 07:35:58 schnaader

1000 cifre sono "piccole" per Schönhage-Strassen che vale davvero la pena usare. Si può dare un'occhiata alla moltiplicazione Toom Cook. gmpy è un wrapper Python per gmp che fornisce queste funzioni.

fonte

2009-05-14 07:34:22

+1, anche se spero che l'OP ne sia a conoscenza. La voce di wikipedia a cui si è collegato spiega molto presto ("inizia a sovraperformare i metodi più vecchi [...] (da 10.000 a 40.000 cifre decimali"). – schnaader

scusate, ne sono a conoscenza, intendevo chiedere "parecchi millesimi di cifre" Io modificherò la domanda: – JPCosta

Non reinventare la ruota. GMP ha un'eccellente implementazione ad alte prestazioni di questo algoritmo e qualsiasi algoritmo scritto in Python puro sarà almeno 100 volte più lento, semplicemente perché Python è un linguaggio interpretato. Usa gmpy per chiamare a GMP dalla tua applicazione Python. Sono anche curioso su quale applicazione stai lavorando che richiede la moltiplicazione di numeri così grandi - potrebbe esserci un modo più semplice per gestire il tuo problema.

Inoltre, come menzionato da altre risposte, "diverse centinaia di cifre lunghe" non è abbastanza lungo da giustificare Schönhage-Strassen (dovresti avere almeno 10000 cifre decimali, probabilmente di più). Alcune varianti di Toom-Cook come Toom-3 sono normalmente utilizzate in questo intervallo. Ancora una volta, non scrivere questo da soli in Python - l'implementazione di GMP è ottimizzata molto attentamente.

fonte

2011-11-03 03:35:25

Beh, che dire di PyopenCL per esempio? – user2284570

Comprendere l'algoritmo di Schönhage-Strassen (enorme moltiplicazione di interi)

risposta

Problemi correlati