Binomial improvements

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


Torbjorn Granlund <tg at gmplib.org> 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
divisor.

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

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

-- 
Torbjörn


More information about the gmp-devel mailing list