algoritmo di Schönhage-Strassen

L'algoritmo di Schönhage-Strassen è un algoritmo di moltiplicazione rapido per grandi numeri interi, sviluppato da e nel 1971. La sua complessità, nella notazione O-grande, è O(n log n log log n). L'algoritmo usa ricorsivi Trasformate di Fourier veloci negli anelli con 22n + 1 elementi. L'algoritmo di Schönhage-Strassen era asintoticamente il più veloce metodo di moltiplicazione conosciuto tra il 1971 ed il 2007, finché non è stato annunciato l' che ha complessità asintotica minore, però al momento raggiunge il vantaggio solo per numeri astronomicamente grandi e non è utilizzato praticamente. In pratica, l'algoritmo di Schönhage-Strassen è più veloce di metodi vecchi come quello di Karatsuba e di Toom-Cook per i numeri da 2215 a 2217 (10.000 a 40.000 cifre decimali). La lo utilizza per valori di almeno 1728 a 7808 word a 64 bit (33.000 a 150.000 cifre decimali), a seconda dell'architettura. C'è una realizzazione in Java dell'algoritmo di Schönhage-Strassen che lo usa per i numeri con più di 74.000 cifre decimali. Applicazioni dell'algoritmo di Schönhage-Strassen includono empirismo matematico come il GIMPS e calcolo di π, così come applicazioni pratiche quali la in cui la moltiplicazione di polinomi con coefficienti interi può essere efficientemente ridotta alla moltiplicazione di grandi numeri interi.