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

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]

This is a bit tricky - Toom-Cook is not an algorithm but an algorithm family, and every single algorithm in that family is asymptotically slower than Schönhage-Strassen; moreover, an algorithm that dynamically chooses epsilon would run aground of the difficulty that now c(e) (which is poorly understood but believed to grow quickly) is a function of the input (c(n)) and not a constant parameter, and so can no longer be subsumed in the big-O. Dcoetzee 11:16, 25 October 2007 (UTC)[reply]

Expansion

I've recently studied and implemented this algorithm and am in the process of expanding it with a lot more detail, enough to enable implementation. Dcoetzee 11:16, 25 October 2007 (UTC)[reply]

Exact bit complexity of Schönhage-Strassen algorithm?

In the lecture notes to his algorithms-course http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/02-fft.pdf (page 2 in the footnote) Prof Jeff Erickson says

"... using $O(n\log n\cdot \log \log n\cdot \log \log \log n\cdot \dots \cdot 2^{O(\log ^{\star }n)})$ ..."

I couldn't find any information on the internet that this should be the real bit complexity of Schönhage-Strassen.

1) Is it true?

and if yes: 2) Why is it true? 3) Is it important to write $2^{O(log^{\star }n)}$ or could there also be a $2^{\log ^{\star }n}$ or just $\log ^{\star }n$ ? 4) Shouldn't it be in wikipedia? Joerg Bader (talk) 19:33, 6 May 2011 (UTC)[reply]

Here's a statement by Knuth in The Art of Computer Programming 2 3rd ed. pp. 311, referencing the bound you've given:

Schönhage and Strassen showed how to improve this theoretic upper bound to O(n log n log log n) in their paper by using integer numbers w to carry out fast Fourier transforms on integers modulo numbers of the form 2^e+1.

Unfortunately, I can't explain the result and have no understanding of the algorithm. I was aware that the algorithm had large coefficients such that it was only suitable for large n's but I didn't realise the explanation of the large coefficients could be so elegantly stated as is done in the footnote you've cited. If someone could sort out these details, it would be a great asset to the article. Skippydo (talk) 21:35, 6 May 2011 (UTC)[reply]