Schönhage-Strassen

[Paul Zimmermann]

       Dear Tsz-Wo,

> Date: Wed, 25 Aug 2010 10:46:22 -0700 (PDT)
> From: Tsz Wo Sze <szetszwo at yahoo.com>
> 
> 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.

thank you for your feedback!

> 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?

very roughly, the FFT length and the modulus should be both about sqrt(n).

> - 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?

the memory usage is about 8n (in addition to the inputs and output). Thus it
is 12n if you count the inputs and output. With 16GB memory you should be able
to multiply two numbers of 1.33GB, thus about 3.2 billion digits.

> - Is there a trade off between running time and memory when choosing the FFT 
> length and the modulus?

the memory does not depend much from the FFT length and the modulus. The
running time decreases when the FFT length increases, until it reaches sqrt(n).

> - 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.)"

the Hybrid NTT might be faster in some ranges of n. However I'd like to see
real timings on the same architecture to be convinced.

Paul Zimmermann