gcd_22

[Victor Shoup]

Regarding the so-called doc bug, if I understand the issue correctly, I don’t think it’s a good idea to add more preconditions to the documentation. In fact, I think that would be a really bad idea.  

> On Aug 25, 2019, at 2:34 AM, niels mller <nisse at lysator.liu.xn--se -wwb> wrote:
> 
> 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.
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at gmplib.org
> https://urldefense.proofpoint.com/v2/url?u=https-3A__gmplib.org_mailman_listinfo_gmp-2Ddevel&d=DwIGaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=vPPV1mqW437RJtXssFXDXg&m=NKF0QnWJUmfxg89L0Z_PQnkD53xG3J-DMkl5rTZQkO0&s=v81U4r_fI3Rlv6qDtur2ADdxaY5esEp664zruTYmAgg&e=