fft interface

Torbjorn Granlund tg at gmplib.org
Wed Oct 17 10:57:30 CEST 2012

  > Internally in gmp, these days the function used for wraparound
  > arithmetic is mpn_mulmod_bnm1 (and mulmod_bnm1_next_size). Which
  > computes modulo B^n - 1, and is useful also below the fft threshold.
  > Have you tried that?
  no, since mpn_mulmod_bnm1 is not in the public interface either.
  Is it planned to put it in the public interface?
As Niels said, mpn_mulmod_bnm1 might be put there.  But mpn_mul_fft will
never be put there, at least not under that name.

(We prefer functions names that describes a function, rather than an

  Note also that mpn_mulmod_bnm1 is currently significantly slower in the FFT
  range (which is what we have in GMP-ECM stage 2):
  # GMP 5.0.5 on AMD Phenom(tm) II X2 B55
  frite% ./speed -s 1000000,2000000,5000000,10000000 mpn_mulmod_bnm1 mpn_mul_fft
  overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
          mpn_mulmod_bnm1   mpn_mul_fft
  1000000    0.512032000  #0.372023000
  2000000    1.068066000  #0.792049000
  5000000    3.608226000  #2.372148000
  10000000    7.304457000  #4.944309000
I doubt that is for the same operand sizes.  Probably 'speed' passes
twice as large operands to mpn_mulmod_bnm1.


More information about the gmp-devel mailing list