Small gcdext_1

[Victor Shoup]

By the way, if you do changed extended Euclid, please remember to respect the documented constraints on the cofactors. This was an issue many years ago, which was eventually resolved, and hopefully will remain so. 

Thanks!

> On Oct 31, 2019, at 12:00 PM, torbjrn granlund <tg at gmplib.xn--org -3hc> wrote:
> 
> nisse at lysator.liu.se (Niels Möller) writes:
> 
>  Updated version below, without input_v and corresponding divisions. Also
>  one of the binary variants use binv. While debugging, I found that the
>  accumulated shift may well exceed GMP_LIMB_BITS (shouldn't be so
>  surprising), but I think it must be < 2 * GMP_LIMB_BITS. And there are a
>  few corner cases.
> 
>  I guess it's possible to do all cofactor shifts as part of the loop, by
>  shifting only one bit per iteration, and making the subtraction
>  conditional on both nubmers being odd. That would be like a single-limb
>  variant of mpn_sec_invert (but with a stop condition to exit early).
>  Unclear if that can be a winner, with less progress per iteration in the
>  main loop. And it may produce a cofactor that's unnecessarily large in
>  the g > 1 case.
> 
>  BTW, the binv/redc part uses an umulhi operation. Maybe we should add
>  that to longlong.h?
> 
> I believe umul_ppmm with unused low result is adequate.  When there are
> separate instructions for low and high parts, we have made sure to
> implement umul_ppmm in such a way that the compiler will eliminate the
> low part.
> 
> How far did you come with gcdext_1?  Do you have any timing improvements
> to report?  :-)
> 
> -- 
> Torbjörn
> Please encrypt, key id 0xC8601622
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-devel