mpn_gcd[ext] interface details

Torbjorn Granlund tg at
Tue May 10 20:30:12 CEST 2011

nisse at (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
wish...  :-)

  > 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 mailing list