Re:Even faster integer multiplication
by userbinator on Tuesday July 15, 2014 @09:17AM
(#8036204)
That reminds me of the fastest known (in terms of number of multiplications) matrix-multiplication algorithm, where the constant factor is so huge that it's of no practical use.
Even the more practical ones e.g. http://en.wikipedia.org/wiki/Strassen_algorithm trades 8 multiplications and 4 additions with 7 multiplications and 18 additions, won't be all that much faster on modern architectures where multiplication is often surprisingly fast (almost the same as addition) and how much data is read/written also matters (memory bandwidth and latency).
Re:Even faster integer multiplication
by arghbleargh on Tuesday July 15, 2014 @12:55PM
(#8037557)
Those are actually matrix multiplications and additions, so it can make a significant difference (e.g. it's way faster to add two 50x50 matrices than to multiply them).
The Fürer algorithm change the loglog term of the complexity to 2^log* which doesn't change anything in practice for workable numbers but it also add a lot to the constant term which is not counted by the big O notation but is very important in practice.