Improvements for mpn_mul_fft

[Torbjorn Granlund]

"Jeunder Yu" <gis91542 at cis.nctu.edu.tw> writes:

  size   old     new
  ====================
  n=13  0.0108  0.0103
  n=14  0.0230  0.0217
  n=15  0.0492  0.0461
  n=16  0.1274  0.1211
  n=17  0.2653  0.2524
  n=18  0.6635  0.6466
  n=19  1.4387  1.3693
  n=20  2.8044  2.6499
  n=21  5.8088  5.4526
  n=22 12.1742 11.4590
  n=23 25.6633 24.1082
  
Still the improvements are considerable for that platform.

  ... therefore, non-recursive and cache locality are very important for
  large n.

I totally agree about the importance of cache locality, but why
is it important to avoid recursiion?  The actual function call
overhead should really be minor, considering the operand size.

  Since the character behavior of fft algorithm was changed (non-recursive and
  better cache locality, lower overhead for large k), we can try to adjust the
  default
  value of MUL_FFT_TABLE and SQR_FFT_TABLE table.
  
Simple:

  cd tune
  make tuneup
  ./tuneup

Then you need to copy the output to gmp-mparam.h and rebuild
everything.

Before we can include your contribution in GMP, we need you to
sign paperwork to sign over your copyright ownership to the FSF.
Are you willing to do that?

-- 
Torbjörn