Cofactor canonicalisation of mpn_gcdext
Torbjorn Granlund
tg at gmplib.org
Mon May 2 11:41:23 CEST 2011
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
More information about the gmp-devel
mailing list