mpn_gcd documentation [Was: Replacing gcd_1 with gcd_11]

Niels Möller nisse at lysator.liu.se
Sun Aug 18 13:04:34 UTC 2019


"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> Ciao,
>
> Il Dom, 18 Agosto 2019 9:44 am, Niels Möller ha scritto:
>> Do we have all needed gcd_11 so we can switch to using it, without
>> performance regressions?
>
> I glanced at mpn/generic/gcd.c
>
> The initial comment says:
> /* mpn/gcd.c: mpn_gcd for gcd of two odd integers.
>
> A comment inside slightly relaxes the conditions with:
>   /* Due to the calling convention for mpn_gcd, at most one can be
>      even. */
>
> ...but I can not find any documented restriction (odd/even) in the manual.

This seems a bit confused, yes. Long ago, mpn_gcd mpn_gcd required one
input odd, but documentation was relaxed with change 71efb0367192 in
2011. The hgcd loops don't care about odd/even, 

To me it looks like the code path mpn_gcd -> gcd_22/gcd_2 will fail if
both inputs to mpn_gcd are even, also before recent changes. And we have
no separate unittests; the gcd tests call mpz_gcd, which takes out
factors of two before calling mpn_gcd.

So we either have to update the docs to say that at least one of the
inputs to mpn_gcd must be odd, or handle common factors of two before
calling gcd_11 and gcd_22.

Regards,
/Niels

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


More information about the gmp-devel mailing list