Question Regarding fft_step_size (int k) in 'tuneup.c' in GMP

Lingchuan Meng lingchuanmeng at
Sun Feb 15 21:00:19 CET 2009

Hi all,

I've been studying and twisting the tuneup program in GMP4.2.4 recently. And
I got a question about the fft_step_size().

fft_step_size (int k)
  mp_size_t  step;

  *step = MAX ((mp_size_t) 1 << (k-1), BITS_PER_MP_LIMB) /
BITS_PER_MP_LIMB;  //what's the special purpose of this line?*
*  step *= (mp_size_t) 1 << k;  //** Is it not good enough just to set step
to 2^k?                             *
  return step;

In addition, I noticed that if I half the step size in fft_step_size(), I
can gain better performance around the point where Toom3 is replaced by SSA.
A plot is provided in attachment, where you can see the threshold generated
by default tuning program (green line) causes a loss since it sets the fft
threshold greater than what it actually is. The one labeled 'tune2' is what
I got by halving the step size. All the values in labels correspond to FFT
thresholds in each case.

Best regards,

Lingchuan Meng
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mul_cmp.png
Type: image/png
Size: 5381 bytes
Desc: not available
URL: <>

More information about the gmp-discuss mailing list