Ce projet consiste à présenter et implémenter l'algorithme de Schönhage-Strassen. C'est un algorithme de multiplication rapide basé sur la FFT.
Cet algorithme est comparé à d'autres algorithmes de multiplication.
- Algorithme standard (Long multiplication) :
longmult - Algorithme de Schönage et Strassen :
ssmult - Algorithme de Karatsuba :
karatsuba
Pour obtenir l'aide sur ssmult, entrez help('ssmult').
De même pour les autres algorithmes.
- Integer multiplication and the truncated product problem
- Polynomial Multiplication and Fast Fourier Transform
- A Rigorous Extension of the Schönhage-Strassen Integer Multiplication Algorithm Using Complex Interval Arithmetic
- Polynomial Multiplication via Fast Fourier Transforms
- Multiplying huge integers using Fourier Transforms
- Arithmétique Algorithmique
- Multiplication algorithm
- Fast Fourier transform
- Cooley–Tukey FFT algorithm
- Schönhage–Strassen algorithm
- Karatsuba algorithm
- Fürer's algorithm
- Understanding Fast Fourier Transform from scratch — to solve Polynomial Multiplication
- Integer multiplication in time O(n log n) - David Harvey
Quentin DESCHAMPS - Ruxue ZENG