Cofactor canonicalisation of mpn_gcdext
tg at gmplib.org
Wed May 4 16:57:37 CEST 2011
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> You should should ask the GMP GCD code developer, I recommend a chat to
> your bathroom mirror. :-)
According to NEWS, the new gcdext code was released in gmp-4.3.
gmp-4.2.4 definitely use the old code. And my mirror image has a very
bad memory for such things.
Then I am not sure what you ask. I thought you asked how the mem reqs
had changed since 4.3. If the only change made was 4.2 -> 4.3, then the
note should reflect that, of course.
> * The documentation said the needed size for gp and sp is given by the
> size of the larger input, un (or un+1 for the pre 4.3 versions). I
> think this was a typo, and that it's always been given by the smaller
> input vn (or vn+1 in pre 4.3 versions), so I changed this. Correct?
> I think you're wrong. I find it unwise to make such a change unless you
> find support for your assumption in old GMP code.
Both the current code and the mpn_gcdext in gmp-4.2.4 starts with
if (un > vn)
mpn_tdiv_qr (tp, up, up, 0, up, un, vp, vn);
If you have analysed the code, I don't mind the change. It sounded as
if you just assumed the docs where wrong, which worried me.
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).
That sound like a good idea.
PS. I have to be somewhat terse in my GMP replies, since I am busy with
More information about the gmp-devel