GCD project status?
tg at gmplib.org
Mon Sep 23 15:11:46 UTC 2019
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
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.
Please encrypt, key id 0xC8601622
More information about the gmp-devel