mpn_gcd[ext] interface details

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   What should the documented requirements be?
>   
> I would suggest that we demand A >= B, and that B is normalised.

I'm leaning towards rather saying that an >= bn, B normalized.

For an > bn, the first step is to replace A by A' = A mod B, and A' < B
for any A. So in this case a requirement that A >= B is a bit pointless,

After this, we're computing either gcd(A, B) (if an == bn) or gcd(A', B)
(if an > bn), with operands of the same number of limbs, where at least
one of them, B, is normalized. Then the current code doesn't care about
the relative order, since neither hgcd2 nor hgcd cares about the
relative order of the inputs.

It's conceivable that some future version may get a little advantage in
the case an == bn, from knowing that A > B. I don't have a strong
opinion about this.

> What exact normalisation requirements does the present code have,
> bp[bn-1] != 0, or stricter?

bp[bn-1] > 0, just like for mpn_tdiv_qr.

> Did we actually break backwards compatibility at some point?

I don't think so, I think we have just relaxed some of the requirements
which were tied to the old implementation.

Regards,
/Niels

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