What is the best multiplication algorithm which has lower time complexity than Strassen's multiplication algorithm??
- 2 Contributors
- forum1 Reply
- 35 Views
- 5 Years Discussion Span
- comment Latest Post by Labdabeta
Labdabeta 182
Technically there is Furer's algorithm, however it has enough overhead that it is rarely used. Indeed it has slightly better asymptotic performance than the Schonage-Strassen and is, in a sense, a generalization thereof.
You can read about it here: http://www.cse.psu.edu/~furer/Papers/mult.pdf
(Credit for the link has to go to rubberman, its taken from a reply to my question in the c++ thread entitled Furer's algorithm)
The complexity of the Schonage-Strassen is O(nlogn*loglogn)
whereas the complexity of furer's algorithm is nlogn*2^(O(log*n))
or equivalently(-ish, read about the iterated logarithm) nlogn*2^O(loglog...loglogn)
. However for most real-world, or even hypothetical mathematics the difference between loglogn
and log*n
is negligible. Unless you are dealing with creating a hypothetical program (for theoretically working with transcomputable numbers) typically Schonage-Strassen is the best there is.
Of course it has been theorized that the lower bound for multiplication is O(nlogn)
however no valid algorithms have been discovered for this. (unless you count Knuth's O(n)
algorithm which is purely theoretical)
Hope this helps.