Cancellation with hgcd / unbalanced mulmod_bnm1

Torbjorn Granlund tg at
Sat Nov 12 19:46:17 CET 2011

nisse at (Niels Möller) writes:

  Torbjorn Granlund <tg at> writes:
  > I think you forgot the save-the-transform trick.
  > Since b is implicitly invariant over several a_i pieces,
  > evaluating b once will be a slight win.
  That's a bit difficult to do with current interfaces, though. And I
  suspect that for this non-extreme unbalancedness, toom42/62/63 is a
  better strategy.
With toom62 we need quite large operands due to costs for the

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


More information about the gmp-devel mailing list