Algoritmo di Schönhage-Strassen

Da Wikipedia, l'enciclopedia libera.

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ò, l'algoritmo di Fürer adesso raggiunge il vantaggio solo per numeri astronomicamente grandi e non è utilizzato praticamente.

In pratica, l'algoritmo di Schönhage-Strassen commincia a superare metodi più 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 come fattorizzazione con le curve ellittiche, nei quali la moltiplicazione di polinomi con coefficienti interi può essere efficientemente ridotta alla moltiplicazione di grandi numeri interi.[5]

Note[modifica | modifica wikitesto]

  1. ^ A. Schönhage, V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
  2. ^ Martin Fürer, "Faster integer multiplication", STOC 2007 Proceedings, pp. 57–66.
  3. ^ MUL_FFT_THRESHOLD in GMP developers' corner. URL consultato il 14 aprile 2013.
  4. ^ An improved BigInteger class which uses efficient algorithms, including Schönhage-Strassen.
  5. ^ Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann. A GMP-based Implementation of Schönhage–Strassen’s Large Integer Multiplication Algorithm, pp.167–174.