What is the best multiplication algorithm which has lower time complexity than Strassen's multiplication algorithm??
rgugopi 0 Newbie Poster
Labdabeta 182 Posting Pro in Training Featured Poster
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.