Talk:Schönhage–Strassen algorithm

Reference to "Fast quantum modular exponentiation"

Not only does this link lead nowhere, which made me have to google it myself, but what does this reference have to do with long integer multiplication ??? Dr. Universe (talk) 22:13, 8 June 2011 (UTC)

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)

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)

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)

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)

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)

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)

I have now researched and resolved this issue, which is explained at length in section 9.5.8 of the Prime Numbers reference. The complexity is not as stated above - in fact, even a very simple recursive FFT-based multiplication algorithm that breaks the inputs into digits of size log n can achieve that complexity. The complexity really is actually O(n log n log log n). It has log log n levels of recursion and each does O(n log n) work. This is possible because recursive multiplications are completely eliminated inside the FFTs by the clever choice of the Fermat ring. I plan to update this article with some discussion of analysis. Dcoetzee 14:25, 14 November 2011 (UTC)

Removed reference to arithmetic complexity

I removed this text from the article:

the arithmetic complexity is O(N log N). (Peter Bürgisser, Michael Clausen and Amin Shokrollahi, Algebraic Complexity Theory, 1997. Springer-Verlag, ISBN 3540605827.)

I don't have access to this source, so it might really say this. However, the term "arithmetic complexity" is not a widely-accepted one (I couldn't find even one explanation of what it is on the web that makes sense in this context). Assuming they're talking about the number of (arbitrary-precision) additions and multiplications performed, without regard for their size, this is pretty silly, since you could easily replace the algorithm by one of "arithmetic complexity" 1 (just multiply the inputs). If on the other hand they're talking about the number of word-size arithmetic operations, then this is simply incorrect (it uses O(n log n log log n) of those). Dcoetzee 14:31, 14 November 2011 (UTC)

Typos

Maybe I read something incorrect, but Google calculator says that 28*31*31 = 24304 and 56088 mod 999 = 144. How to obtain 3141 from 28,31,31? Thanks. 31.42.239.14 (talk) 11:59, 20 February 2013 (UTC)

You have to add it with the right positional weightings: 28*100 + 31*10 + 31 = 3141. Cxxl (talk)

Fürer exists now

In fact source code is even there. That library is a big one, and appears to be used. https://github.com/orcca-uwo/BPAS/issues/1 here is even paper in acm. https://dl.acm.org/doi/10.1145/3326229.3326273 Valery Zapolodov (talk) 08:22, 29 March 2023 (UTC)

Can we move discussion of specific projects/libraries out of the lead section?

These should IMO be moved to a new section specifically about practical implementations. The discussion in the lead is distracting, not particularly helpful to readers, and a magnet for self-promotion by anyone who has implemented this or related algorithms. –jacobolus (t) 21:41, 6 April 2023 (UTC)