patternMajor
What is the fastest algorithm for multiplication of two n-digit numbers?
Viewed 0 times
thewhatmultiplicationnumbersalgorithmtwoforfastestdigit
Problem
I want to know which algorithm is fastest for multiplication of two n-digit numbers?
Space complexity can be relaxed here!
Space complexity can be relaxed here!
Solution
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 :
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 :
- Fürer's algorithm
- FFT based multiplication of large numbers
- Fast Fourier transform
- Toom–Cook multiplication
- Schönhage–Strassen algorithm
- Karatsuba algorithm
Context
StackExchange Computer Science Q#16226, answer score: 24
Revisions (0)
No revisions yet.