Talk:Schönhage-Strassen algorithm

From Wikipedia, the free encyclopedia

[edit] 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)

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

Edit: Knuth also discusses the problem. He gives the complexity of Toom-Cook as O(c(e) n^1+e), not O(n^1+e); and of course, it's the function c that causes the trouble. The article on Toom-Cook should be corrected. Fredrik Johansson 21:42, 17 August 2006 (UTC)

Toom-Cook is slower than Schönhage-Strassen in the limit -- even at practical sizes. The GMP project switches from T-C to S-S at a certain size, because from then on it's more efficient. I did add a reference, though, per your {{fact}} tag. Regardless, there's no need for excessive justification here: O(n log n log log n) is contained in O(n^1+e); it just happens that we know a more particular limit for S-S. CRGreathouse (talk | contribs) 23:33, 17 August 2006 (UTC)

Thanks, that clears things up. I read up on Knuth, and he certainly says so. I was perhaps a bit thrown off by the fact that the O(n^1+e) is stated in at least two other articles. I saw your edits to Tom-Cook multiplication, I could have liked to see a reference for the error bound. I would also suggest that you have a look on the two other articles and perhaps add some clarification to them. The articles in question are Multiplication algorithm and Computational complexity of mathematical operationsBfg 12:06, 18 August 2006 (UTC)