Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

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

> Hmm. The doc also says
>
>      The areas {XP, XN+1} and {YP, YN+1} are destroyed (i.e. the input
>      operands plus an extra limb past the end of each).
>
> I wonder if it still needs that extra limb. At least mpn_gcd doesn't
> need it anymore (and the documentation says so).

I've fixed the documentation, and I've changed mpz_gcdext to no longer
allocate these extra limbs. It seems to still work fine.

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.

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

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.