fft interface

[Zimmermann Paul]

       Torbjörn,
       
> 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
> algorithm.)

ok.

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

no it seems it is for similar operand sizes. I instrumented the source code
and got:

mpn_mul_fft pl=1007616 nl=1000000 ml=1000000
mpn_mulmod_bnm1: rn=1000000 an=1000000 bn=1000000

However with s=1007616 I get better timings for mpn_mulmod_bnm1:

frite% ./speed -s 1007616 mpn_mul_fft mpn_mulmod_bnm1
overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
          mpn_mul_fft mpn_mulmod_bnm1
mpn_mul_fft pl=1007616 nl=1007616 ml=1007616
mpn_mulmod_bnm1: rn=1007616 an=1007616 bn=1007616
1007616    0.368023000  #0.344022000

In fact it seems I should compare with mpn_mulmod_bnm1_rounded, which seems to
use the best fft size greater or equal to the wanted size (speed mpn_mul_fft
does this automatically):

frite% ./speed -s 1000000,2000000,5000000,10000000 mpn_mul_fft mpn_mulmod_bnm1_rounded
overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
          mpn_mul_fft mpn_mulmod_bnm1_rounded
mpn_mul_fft pl=1007616 nl=1000000 ml=1000000
mpn_mulmod_bnm1: rn=1015808 an=1000000 bn=1000000
1000000    0.368023000  #0.304019000
2000000    0.780048000  #0.752047000
5000000    2.392149000  #2.212138000
10000000    4.944309000  #4.828301000

Paul