Binomial improvements

Torbjorn Granlund tg at
Sun Dec 11 21:37:50 CET 2011

Torbjorn Granlund <tg at> writes:

  Unlike my bdiv_bin_uiui code, this code puts all multiplies and
  "divides" on the same dependency chain.  This might hurt performance on
  some machines (with good multiply throughput and long latency).
Wait a minute...

Multiply is associative and commutative, even in a ring (mod B).

Therefore we can multiply the dividend together separately from the

But that means for the divisor, that we always multiply 1..k ^(-1) (mod

We could therefore tabulate these values, and avoid much multiplying!


More information about the gmp-devel mailing list