mpn_gcd[ext] interface details
tg at gmplib.org
Tue May 10 20:30:12 CEST 2011
nisse at lysator.liu.se (Niels Möller) writes:
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.
I think you can decide this, considering my input to the degree you
> 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.
Note that the old documentation does not speak at all about
I have not had time to check the implementation, but if it too did not
require any normalisation, then it seems we broke backwards
compatibility, furthermore without flagging properly about it...
I hope the old docs where wrong (or that I, in my present stay of panicy
stress misread it) .
More information about the gmp-devel