Talk:Schönhage–Strassen algorithm

Asymptotically the fastest multiplication method

Is this really the asymptotically fastest multiplication method?

This is inconsistent with Toom-Cook multiplication which in the limit becomes O(n). Bfg 20:54, 17 August 2006 (UTC)[reply]

Of course, for any fixed Toom-Cook scheme, Schönhage-Strassen is asymptotically faster. But even an algorithm that dynamically chooses increasing Toom-Cook levels based on the size of the input would be slower. It is really the O(n^1+e) complexity estimate for Toom-Cook that is wrong, because it considers only the complexity of subproducts and ignores all the additions and multiplications by small factors, which grow in number very quickly. A more precise description of the dilemma can be found in Crandall & Pomerance - Prime Numbers: A Computational Perspective. They give the problem of figuring out the real complexity of Toom-Cook as a research problem (problem 9.78.). Fredrik Johansson 21:42, 17 August 2006 (UTC)[reply]