Cofactor canonicalisation of mpn_gcdext
Niels Möller
nisse at lysator.liu.se
Mon May 2 11:15:50 CEST 2011
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.
More information about the gmp-devel
mailing list