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)

You literally cannot see that https://bpaslib.org/ has a valid TLS certificate, as you can see in the CT log: https://crt.sh/?id=8828442498 Yet you are arguing GMP that implemented SS algorithm should not be mentioned. That is very strange logic. Promoting GNU libraries is a good thing. Also, it is better than not mentioning reference implementation. Instead this article should be expanded by mentioning HW implementations, I am pretty sure Intel uses SS inside. Oh, and BTW, the reason we have to write it all here is because someone just permadeleted https://handwiki.org/wiki/F%C3%BCrer%27s_algorithm Valery Zapolodov (talk) 03:32, 7 April 2023 (UTC)

It should be mentioned, in a dedicated section about practical implementations. This just should not be the primary focus of the lead section, where it is a huge distraction for readers. The current lead section here is full of jargon and technical details which are not really that helpful for establishing basic definition, explanation, or context. This article should ideally be at least slightly accessible for even completely nontechnical readers; currently it’s pretty much incomprehensible to anyone who doesn’t have an undergraduate computer science degree or equivalent experience. –jacobolus (t) 06:42, 7 April 2023 (UTC)

No, most people come here to look up implementations. Writing assembly for this algorithm is too hard. BTW, I did not mention yesterday that https://en.wikipedia.org/wiki/Multiplication_algorithm has Covanov name mentioned, so "student" was simply wrong. Some things are complex. It is what it is. Valery Zapolodov (talk) 16:31, 7 April 2023 (UTC)

Okay, I gave rewriting the lead a shot. I think it’s a lot clearer and less cluttered now, while still conveying the main information necessary to introduce the subject and provide basic context. Sorry I kept tweaking it so many times; I’m not just trying to clutter up the edit history.

As I said, I think it would be fine to add a section somewhere in the article discussing more details about the GNU Multi-Precision Library etc. But I found them distracting in the context of the lead section. –jacobolus (t) 22:32, 7 April 2023 (UTC)

Will you write implementation section? Wanna have Intel stuff too, you will have to look into patents I imagine. GMP-ECM is not GMP. It is another library done by Inria. Valery Zapolodov (talk) 02:37, 8 April 2023 (UTC)

BTW, you do understand GMP-ECM library was used to find 54-digit factor of F12? http://caramel.loria.fr/f12.txt (that one is indeed insecure https). Valery Zapolodov (talk) 01:44, 9 April 2023 (UTC)

Article degradation

After a series of several hundred edits in July, this article has been degraded in a number of areas. In particular, prose style and general understandability. (Compare the current revision with [1].) While the old article was not especially great either, at least it was vaguely understandable. I don't know what the path forward is, but the current state of affairs strikes me as untenable. It might be worth restoring the pre-July version, and then incrementally adding any salvageable details from the revision. Tito Omburo (talk) 17:59, 13 December 2023 (UTC)

I tend to agree that the changes made the article significantly less accessible. The IP editor who made them was apparently expecting a much more advanced audience than the previous version did. I think it's worth trying to explain this for the widest practical audience at least at the beginning. –jacobolus (t) 01:05, 14 December 2023 (UTC)

I found that just reading the full algorithm from Crandall and Pomerance, without reading any of their explanation, is actually more informative than reading the first sections of the article. The biggest problem for me is that this article spends too much space in the early sections discussing things inline that are not that essential to a proper understanding. The FFT is described inline, the term "NTT" is confusing. Various (I guess) optimizations are done inline, rather than deferred. Another problem is that parts of it seem to be mathematically incorrect. For example, the ring that is referred to as $GF(2^{n}+1)$ need not be a field. The more I look, the more problems there are. Tito Omburo (talk) 11:06, 14 December 2023 (UTC)

I agree that the current state of this article is extremely hard to understand. There's many issues, especially in the "Details" section:

• Use of unexplained, inconsistent across and within sections, and frankly chaotic mathematical notation (even in the first three sentences of the Details section, are the "digits" x_i and y_i, or are they a_i and b_i? What is \delta^{(n)}? \xi? $N(N)=2^N+1$? The last half of the "Details" section uses complex numbers, which are not used in Schönhage-Strassen, and are never mentioned afterwards. Mentioning "fourier basis" without explaining the concept. Using "For example GF(p), where p is a prime, gives {1, 2, ..., p - 1}" to explain what a root of unity is. Total chaos.)
• Dozens and dozens of grammatical mistakes ("This mean, one can use weight", "one get the desired coefficients.", "Same FFT algorithms can still be used", "First product gives contribution", "depending on whether fft one use normalize data or not", "One multiply by 2^{-m}", "where one have values", "This is Fermat number.", among many, many other examples)
• Inconsistently use LaTeX versus just plain text ("This can also be written as: fft(a * b) = fft(a) ● fft(b).", "By finding ifft (polynomial interpolation)")
• The "Pseudocode" section is incomprehensible. I've been a professional software engineer for 17 years, and have the relevant mathematical background (basic ring theory and number theory). I found it completely unusable. It somehow refers to nonexistent equations?? "Weight both coefficient vectors according to (2.24)", "Apply the counterweights to the ⁠c_k according to (2.25)" This seems to have been copied from somewhere and unceremoniously dumped...

I'd have fixed at least the grammatical errors, but honestly, this article needs an almost complete rewrite by someone who understands the material well enough to explain it coherently. The overview section seems fine, the "Description" can be improved but is passable, but the rest of the article should be rewritten from scratch. As it is, it is far below the quality one wishes for a Wikipedia article on such a famous algorithm. Flebron (talk) 21:03, 6 August 2024 (UTC)

Pretty similar to my own assessment. I wrote the "Description" section, which could be a useful starting point for a rewrite. Tito Omburo (talk) 21:18, 6 August 2024 (UTC)