t...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
