Improvements for mpn_mul_fft

Torbjorn Granlund tege at
Sun Oct 31 12:03:03 CET 2004

"Jeunder Yu" <gis91542 at> 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
  value of MUL_FFT_TABLE and SQR_FFT_TABLE table.

  cd tune
  make tuneup

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

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?


More information about the gmp-devel mailing list