fft interface

[Zimmermann Paul]

       Niels,

thank you for your answer.

> From: nisse at lysator.liu.se (Niels Möller)
> Date: Wed, 17 Oct 2012 10:22:43 +0200
> 
> Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:
> 
> > several applications using GMP (in particular GMP-ECM) use the internal fft
> > functions (mainly mpn_mul_fft and mpn_fft_best_k) for multiplication modulo
> > 2^N+1. This saves a factor of two with respect to mpn_mul_n if for example you
> > know the lower part of a N-bit product, and you want to compute the upper part.
> 
> 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?

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

> > However those functions are still internal. Is it planned in the future to
> > make them (or similar functions) part of the public interface?
> 
> For the wraparound trick, I think something like mulmod_bnm1 is more
> suitable for a public interface than the fft functions. Not sure if the
> current interface is mature enough to qualify.

for GMP-ECM, I guess we can use both multiplication mod B^N+1 or B^N-1.

> And we totally lack interfaces for invariance (and such interfaces don't
> have to be fft-specific).

Best regards,
Paul