Multiplication rapide & FFT

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.

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.

Références

Documents

• 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

Liens

• 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

Auteurs

Quentin DESCHAMPS - Ruxue ZENG