What is the best multiplication algorithm which has lower time complexity than Strassen's multiplication algorithm??

2
Contributors
1
21
Views
4 Years
Discussion Span
Last Post by Labdabeta

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.

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)