gcd_22

[Niels Möller]

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

> Now what?

1. Update mpn_gcd.c and other callers of gcd_11 to call the new
   functions (like in the patch I posted few days ago). Watch out for
   performance regressions.

2. Consider alternative entry points. Allowing one even operand would
   simplify mpn_gcd, at least. Entrypoints with initial reduction (like
   current mpn_gcd_1, but with a more carefully tuned threshold).

3. Fix the doc(?) bug in mpn_gcd, regarding even inputs.

> Should we have gcd_33, gcd_44, and gcd_55 also?

I think it would be more beneficial to optimize hgcd2. I think one could
have a loop use table lookup on the most significant bits, to get an
approximate quotient. Not sure if it's reasonable to do a
count_leading_zeros per iteration, or if one should have some other
book-keeping if (approximate) leading bits, or maintain normalization
within the loop.

E.g., 3-limb gcd should typically boil down to one hgcd2, a couple of
3:1 mul_1/addmul_1, and one call to gcd_22. It's not obvious that a
gcd_33 using the binary algorithm will be faster.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.