GCD project status?

[Torbjörn Granlund]

tg at gmplib.org (Torbjörn Granlund) writes:

  I went ahead and pushed a hgcd2.c with _METHOD = 4 and _METHOD 5.  The
  former tables quotients and neeeds one multiply per div1 call and the
  latter tables inverses and needs 2 multiplies per div1 call.

I pushed improved versions.

Instead of detecting potential problematic operands ahead of time, both
methods now try its division-free algorithm, carefully avoiding
overflow.  If the remainder is not in range, they fall back to division.

  The quotient table method isn't pretty.  It can surely be improved.  It
  uses a very large table and gets poor throughput.  It also has only
  about 80% branch hit rate, which is not good enough.

Now 90%.  But the table is still the same huge size.

  The inverse table method is more mature, I believe.  It has much smaller
  tables and with the default table size (256 2-byte entries) it gets a
  branch hit rate of 97%.  Doubling the table results in 98.5% rate.

Now 99.74% for the smaller table.  The larger table is no longer useful
and is gone.  The default is now a 64-byte table with 99.5% division
avoidance.

It is easier to see that the new variants are correct; if the few
arithmetic operations do not overflow (which I claim to be true) and if
the remainder is in range [0,d-1] then the result will be correct.


-- 
Torbjörn
Please encrypt, key id 0xC8601622