0

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

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

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.