GCD project status?

[Niels Möller]

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

> I feel we've achieved much of the possible speedup for gcd now.

How much speedup have we achieved?

> But what more can we do before we are completely done for now?
> Let me try to list it:
>
>
> * Add entry points for gcd_11 allowing even operand(s).
> * Add entry points for gcd_22 allowing even operand(s)?
> * Make generic/gcd_1.c call gcd_11 and get rid of */gcd_1.asm.

And review other call sites for mpn_gcd_1.

> * Consider adding gcd_33, etc, and also the basecase code Marco and
>   Torbjorn worked on.
>
> * Speed up div1, presumably with a table-based approach.
>
> * Copy the div1/div2 code to hgcd2_jacobi.c (or put it in its own file,
>   or in gmp-impl.h).
>
> * Tune HGCD_DIV2_METHOD?
>
> * Update lots of gmp-mparam.h files with HGCD_DIV{1,2}_METHOD and
>   GCD_DC_THRESHOLD (the latter has move a lot!)

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?

> * 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.

> Did I forget something?

* Try out left-to-right binary hgcd2.

* Fix doc or implementation regarding mpn_gcd with even inputs.

Regards,
/Niels

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