What is the fastest algorithm for multiplication of two n-digit numbers?

Question Detail: 

I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!

Asked By : Andy

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16226

Answered By : avi

As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$

Other algorithms which are faster than Grade School Multiplication algorithm are Karatsuba multiplication which has a time complexity of $O(n^{\log_{2}3})$ ≈ $O(n^{1.585})$ and Toom 3 algorithm which has a time complexity of $Θ(n^{1.465})$

Note that these are the fast algorithms. Finding fastest algorithm for multiplication is an open problem in Computer Science.

References :

1. Fürer's algorithm
2. FFT based multiplication of large numbers
3. Fast Fourier transform
4. Toom–Cook multiplication
5. Schönhage–Strassen algorithm
6. Karatsuba algorithm