Hacker News Reader

The improvement is only theoretical. The Fürer algorithm is quicker than Schönhage-Strassen only for impractical numbers and no arbitrary precision toolkit use it as far as I know.

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.

View on HN

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).

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).

Reply on news.ycombinator.com