Cofactor canonicalisation of mpn_gcdext

[Torbjorn Granlund]

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

  I've fixed the documentation, and I've changed mpz_gcdext to no longer
  allocate these extra limbs. It seems to still work fine.
  
Should we perhaps keep a compatibility note in the documentation, since
lean allocation in applications will introduce nasty buffer overrun bugs,
if linked to GMP 4.3 or older?

  When looking at mpz_gcdext, I wonder what's the best strategy for the
  case that U < V and the cofactor corersponding to U is wanted? If I
  understand the currentt mpz_gcdext correctly, it calls with U and V
  swapped, to get the cofactor T, and then computes
  
    S = (G - T V) / U
  
  This is a multiply of size un × vn followed by a divexact of (un+vn) /
  un.
  
  I imagine this may be pretty good when vn is much larger than un, since
  it lets mpn_gcdext work with the smaller cofactor T of size un during
  all the reductions, and then there's a single computation at the end
  involving numbers of size vn.
  
  But when U and V are of about the same size (in particular, when un ==
  vn and U < V), it should be faster to compute the desired cofactor
  directly, which would need some alternative or generalized mpn_gcdext.
  
  Current mpn_gcdext requires that U >= V, and starts by replacing U by U
  mod V (quotient discarded, since the cofactor S is invariant under this
  reduction). For U < V, one would do an initial division V / U, and in
  this case the quotient is needed for proper initialization of the
  cofactor variable.
  
Perhaps mpz_gcdext (or some mpn_gcdext2) could perform an initial step
(i.e., division) for this case, to avoid adding overhead to mpn_gcdext?

  I'm afraid any improvment would involve some non-trivial tuning based on
  the relative size of un and vn.
  
I agree.  :-)

-- 
Torbjörn