L'algoritmo di Schönhage-Strassen è un algoritmo di moltiplicazione rapido per grandi numeri interi, sviluppato da Arnold Schönhage e Volker Strassen nel 1971.[1] 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'algoritmo di Fürer che ha complessità asintotica minore,[2] 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 GNU Multi-Precision Library lo utilizza per valori di almeno 1728 a 7808 word a 64 bit (33.000 a 150.000 cifre decimali), a seconda dell'architettura.[3] C'è una realizzazione in Java dell'algoritmo di Schönhage-Strassen che lo usa per i numeri con più di 74.000 cifre decimali.[4]
Applicazioni dell'algoritmo di Schönhage-Strassen includono empirismo matematico come il GIMPS e calcolo di π, così come applicazioni pratiche quali la fattorizzazione con le curve ellittiche in cui la moltiplicazione di polinomi con coefficienti interi può essere efficientemente ridotta alla moltiplicazione di grandi numeri interi.[5]
Note
modifica- ^ A. Schönhage, V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
- ^ Martin Fürer, "Faster integer multiplication (PDF) (archiviato dall'url originale il 25 aprile 2013).", STOC 2007 Proceedings, pp. 57–66.
- ^ MUL_FFT_THRESHOLD, in GMP developers' corner. URL consultato il 14 aprile 2013 (archiviato dall'url originale il 24 novembre 2010).
- ^ An improved BigInteger class which uses efficient algorithms, including Schönhage-Strassen..
- ^ Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann, A GMP-based Implementation of Schönhage–Strassen's Large Integer Multiplication Algorithm (PDF), su loria.fr, pp. 167-174.
