GCD project status?

[Torbjörn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  How much speedup have we achieved?

I don't know.  I just observed the GCD_DC_THRESHOLD to change a lot, and
that is a good sign.

  Looks like GCD_DC_THRESHOLD gets higher on many machines, but lower on a
  few? I now realize that the way tuneup currently works, tuning of HGCD_*
  and GCD_* do *not* take the tuned HGCD2_*_METHOD into account. To fix
  that, tuneup build needs mpn_hgcd2 to jump via a function pointer. Or is
  there a better way to do that?

Dunno.

Ideally, one would compile hgcd2.c in all possible variants (presumable
through hand-crafted hgcd2-1-1.c, hgcd2-2-1.c, etc., and then call the
selected hgcd2's entry point through a function pointer for further
measuring.  Using a function for div1/div2 would disturb the
measurements a lot, I think.

  > * Make gcdext great again (as great as gcd).

  That means asm gcdext_11 and gcdext_22? In the Lehmer-range, I think
  it's as good as gcd. Then the subquadratic range gcdext is suboptimal,
  but that's a different project.

Asm gcdext_11, _22, and prhaps some more should be done, I think.

I'm pretty confused about the algorithms used for gcdext.  Is it at all
helped by our hgcd2 improvements?

What is suboptimal about gcdext for large operands?

  * Try out left-to-right binary hgcd2.

I had not realised you meant left-to-right.  I thought you talked about
right-to-left.  Interesting!

  * Fix doc or implementation regarding mpn_gcd with even inputs.

OK.

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