Cancellation with hgcd / unbalanced mulmod_bnm1

Niels Möller nisse at lysator.liu.se
Sat Nov 12 20:50:44 CET 2011


Torbjorn Granlund <tg at gmplib.org> writes:

> Perhaps one should look into a specialised toom-like primitive that
> directly takes the cancellation into account?  This should not be hard
> to investigate.

Like, extending toom_mullo beyond tomm2 and Mulders' trick? Or do you
think one can do something useful with a modulo which is not a power of
two (and with less overhead than current mulmod_bnm1)?

For mullo, one could easily omit interpolation for the high limbs, but
to really save more than linear work, one would like to omit the high
part (or all) of the product for the infinity point, but then one can't
use that value in interpolation for the lower limbs. So it may be a bit
tricky.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.


More information about the gmp-devel mailing list