Cofactor canonicalisation of mpn_gcdext

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Torbjorn Granlund <tg at gmplib.org> 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.

-- 
Torbjörn