Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

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

> 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).

I'm about to check in the attached mpz/gcdext.c. It does two things,
both related to the tmp allocations.

1. In the common case, allocates space corresponding to the smaller
   input (called vn in earlier mail, and bsize in this code), rather
   than un.

2. In the uncommon case V == 0,, construct the return values without any
   tmp allocations at all. I don't think this case is very important to
   optimize, but since G = U in this case, the correct G doesn't fit in
   tmp_gp as allocated for the common case, and hence it makes sense to
   me to handle it specially.

Passes make check. But maybe I should wait until the testing system
builds the main gmp tree?

As for the documentation, I'll change the compatibility note to say
that the older versions required un+1 allocation (rather then the
smaller vn+1)? That was the documented requirement, I don't think it
makes any sense, but maybe the old code really overwrites un - vn limbs
that will never hold any real data. I don't really feel like doing a
more thorough investigation of the behaviour of ancient versions.

Regards,
/Niels

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: gcdext.c
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20110504/458d8d1a/attachment.c>
-------------- next part --------------

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