Schönhage-Strassen
Tsz Wo Sze
szetszwo at yahoo.com
Wed Aug 25 19:46:22 CEST 2010
Hi,
First, thanks to the authors of "A GMP-based Implementation of
Schönhage-Strassen’s Large Integer Multiplication Algorithm". The paper
provides many useful information. Some questions:
- Given n, the number of bits of the operands, what is the best choice of the
FFT length and the Schönhage-Strassen modulus?
- What is the memory requirement for running Schönhage-Strassen? Supposed there
are 16GB memory. What is the largest n that the machine can support?
- Is there a trade off between running time and memory when choosing the FFT
length and the modulus?
- I supposed GMP is using Schönhage-Strassen for large integer multiplication.
However, the author of y-cruncher claims that Hybrid NTT is faster than SSA in
practice; see the quote below. Do you agree?
http://www.numberworld.org/y-cruncher/algorithms.html
"The difference between the run-time complexities of Hybrid NTT and SSA is on
the order of double-logarithms. However, SSA has a much larger Big-O constant -
so large that Hybrid NTT is a lot faster for any attainable size despite having
a slightly inferior complexity. (Of course, this could change if there are any
new ground-breaking optimizations that apply to SSA but not to Hybrid NTT.)"
Regards,
Tsz-Wo
More information about the gmp-discuss
mailing list