Talk:Schönhage–Strassen algorithm

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's priority scale.

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

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

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

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 operations Bfg 12:06, 18 August 2006 (UTC)[reply]