GMP 4.4 remaining tasks

Torbjorn Granlund tg at
Mon Dec 7 21:48:12 CET 2009

bodrato at 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 mailing list