en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
3 corrections found
By using FFT (fast Fourier transform), used in the original version rather than NTT (Number-theoretic transform), with convolution rule; we get
This reverses how Schönhage–Strassen works. The original algorithm is a modular/Fermat-style FFT over rings modulo 2^n+1, i.e. the number-theoretic approach, not an ordinary complex FFT used “rather than NTT.”
Full reasoning
Reliable descriptions of the Schönhage–Strassen method say its transforms are carried out modulo numbers of the form (2^N+1), not as a standard complex-number FFT.
- The GNU MP manual says its Schönhage–Strassen-style FFT multiplication follows Schönhage and Strassen and that the "evaluations, pointwise multiplications, and interpolation are all done modulo 2^N'+1".
- The Archive of Formal Proofs describes a verified implementation "based on the original paper by Schönhage and Strassen" and explicitly says it adapts Number Theoretic Transforms (NTTs) to rings that need not be fields.
So the article's wording is backwards: Schönhage–Strassen does not use an ordinary FFT instead of NTT. Its key idea is exactly to perform FFT-like transforms in modular rings, i.e. the number-theoretic setting.
2 sources
- FFT Multiplication (GNU MP 6.3.0)
At large to very large sizes a Fermat style FFT multiplication is used, following Schönhage and Strassen ... The evaluations, pointwise multiplications, and interpolation are all done modulo 2^N'+1.
- Schönhage-Strassen Multiplication - Archive of Formal Proofs
We give a verified implementation of the Schönhage-Strassen Multiplication on Integers based on the original paper by Schönhage and Strassen ... For verifying correctness, we adapt the formalization of Number Theoretic Transforms (NTTs) by Ammer and Kreuzer to the context of rings that need not be fields.
By letting N = 2 k − 1, one have the maximal number in a binary number with k + 1 bits.
The maximum unsigned value representable with k+1 bits is 2^(k+1)−1, not 2^k−1.
Full reasoning
For unsigned binary integers, the standard range for an (n)-bit value is 0 to (2^n-1) inclusive. So if a number has (k+1) bits, its maximum value is (2^{k+1}-1).
The claim in the article says the maximum ((k+1))-bit value is (2^k-1), which is off by a factor of two in the highest power of 2. (2^k-1) is instead the maximum value representable with only k bits.
1 source
- CSC 270: Data Representation
In general, we can use n bits to represent an integer from 0 to 2^n - 1 inclusive, e.g. 8 bits gives us 0 to 255.
Notice that N = 2 M + 1 = 2 2 L + 1, for some L. This makes N a Fermat number.
Numbers of the form 2^M+1 are Fermat numbers only when M itself is a power of two. Schönhage–Strassen works modulo 2^N+1 for a chosen N; it is not restricted to Fermat numbers.
Full reasoning
A Fermat number has the special form (2^{2^m}+1). So a number of the form (2^M+1) is a Fermat number only if (M=2^m) for some integer (m).
The Schönhage–Strassen method, however, is described in standard references simply as working modulo (2^N+1) for a suitable chosen (N)**; there is no general requirement that this exponent be a power of two. So the article's statement that (2^M+1) is always equal to (2^{2^L}+1) "for some L" is false in general.
2 sources
- Fermat Number -- from Wolfram MathWorld
The much more commonly encountered Fermat numbers are a special case, given by the binomial number of the form 2^(2^n)+1.
- FFT Multiplication (GNU MP 6.3.0)
The multiplication done is x*y mod 2^N+1, for a given N ... A k parameter controls the split, with an FFT-k splitting into 2^k pieces of M=N/2^k bits each.