GMP 4.4 remaining tasks
tg at gmplib.org
Mon Dec 7 21:48:12 CET 2009
bodrato at mail.dm.unipi.it writes:
> For GMP 4.4 we need mpn_invert code that uses FFT wraparound. If I
> understand it correctly, your mulmid code will help in a (large) operand
> size interval before FFT kicks in.
I'd like to try the mod_bnm1 wraparound... It should be slightly faster
than (B^n+1) for big sizes, and it should be a gain wrt plain mul far
earlier than FFT.
Unfortunately this wraparound is not described (yet) in the book... I'll
need much more attention :-)
The wrapping multiplication for mpn_invert and mpn_binvert are of the
kind 2n x n. Using mulmod_bnm1 for that is not that great. (We might
try other polynomials, though.)
There is an important place for mulmod_bnm1 where mul mod (B^n+1) is
used today: division with remainder. At least mu_div_qr and mu_bdiv_qr
will benefit greatly from that.
More information about the gmp-devel