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]

This is a good question and I'd have to study the sources in some detail to sort out the true answer. I believe the answer depends on what you consider to be a primitive (constant time) operation, but in a manner that is unclear to me. Alternatively, these may both be valid upper bounds, and the one cited in this article is simply tighter, in which case we should of course give the tighter bound (in references that give proofs, they'll often prove a looser bound because the proof is easier). Dcoetzee 23:55, 6 May 2011 (UTC)[reply]