Cofactor canonicalisation of mpn_gcdext

Torbjorn Granlund tg at
Wed May 4 16:57:37 CEST 2011

nisse at (Niels Möller) writes:

  Torbjorn Granlund <tg at> writes:
  > You should should ask the GMP GCD code developer, I recommend a chat to
  > your bathroom mirror.  :-)
  According to NEWS, the new gcdext code was released in gmp-4.3.
  gmp-4.2.4 definitely use the old code. And my mirror image has a very
  bad memory for such things.
Then I am not sure what you ask.  I thought you asked how the mem reqs
had changed since 4.3.  If the only change made was 4.2 -> 4.3, then the
note should reflect that, of course.

  >   * The documentation said the needed size for gp and sp is given by the
  >     size of the larger input, un (or un+1 for the pre 4.3 versions). I
  >     think this was a typo, and that it's always been given by the smaller
  >     input vn (or vn+1 in pre 4.3 versions), so I changed this. Correct?
  > I think you're wrong.  I find it unwise to make such a change unless you
  > find support for your assumption in old GMP code.
  Both the current code and the mpn_gcdext in gmp-4.2.4 starts with
  something like
    if (un > vn)
      mpn_tdiv_qr (tp, up, up, 0, up, un, vp, vn);
If you have analysed the code, I don't mind the change.  It sounded as
if you just assumed the docs where wrong, which worried me.

  mpz_gcdext still allocates un limbs for both gp and sp (and did allocate
  un+1 until my checkin yesterday). I'll try reducing that to vsize, to
  see what happens (and gsize == usize actually happens in the case vsize
  == 0, which is allowed by mpz_gcdext but not by mpn_gcdext).
That sound like a good idea.

PS. I have to be somewhat terse in my GMP replies, since I am busy with
course work.


More information about the gmp-devel mailing list