GMP 4.4 remaining tasks

Torbjorn Granlund tg at gmplib.org
Tue Dec 8 11:09:13 CET 2009


bodrato at mail.dm.unipi.it writes:

  >> I suppose we could write a special mulmod_bnm1 for the degenerate case
  >> where 2bn < rn.
  >
  > I don't think you need any interesting special handling for that case.
  > What happens is just that the top-level split into b mod (B^n + 1) and b
  > mod (B^n - 1) are nops, where the "normal" case needs an add and a sub.
  > Current code handles that (even though Marco has marked that handling as
  > "ALLOW_MISUSE...).
  
  The additional restrictions given by "#define ALLOW_MISUSE 0", affect size
  an only. The product with (an > rn/2) && (an => bn) will work anyway.
  
  My goal, when I modified mulmod_bnm1, was to allow the case (an+bn)<=rn.
  So that mulmod_bnm1 can be used for the full product.
  It is _not_ slower than current mpn_mul_fft_full...
  
  The "misuse" forbidden by the definition above are _very_ degenerate:
   - (an+bn) < rn/2

That might happen if we want to do full multiplication, given the nature
of mpn_mulmod_bnm1_next_size...

Talking about mpn_mulmod_bnm1_next_size.  My simple-minded rounding to
the next multiple of 16 for all sizes under MUL_FFT_MODF_THRESHOLD could
perhaps be trimmed to have some size dependency:

1. I suspect we should round 9,10,11 to just 12, and that some values
   under 24 should be rounded to 24.

2. If we ever consider writing mpn_bc_mulmod_bn{m,p}1 in assembly, it
   would be nice to make sure the sizes are really in a schoolbook
   range.  We could enforce that by rounding to a larger multiple for
   large operands (specifically, that the down-shifted even value is in
   the schoolbook range).  Silly or clever?

   We should realise of course that mpn_bc_mulmod_bnm1 will be called
   just once and that mpn_bc_mulmod_bnp1 will be called once for small n
   and zero times for large n.  Optimised mpn_bc_mulmod_bn{m,p}1
   therefore only matter for smallish operations.

-- 
Torbjörn


More information about the gmp-devel mailing list