mpz reuse test takes too much time
nisse at lysator.liu.se
Sat Dec 3 11:13:23 UTC 2016
Marc Glisse <marc.glisse at inria.fr> writes:
> On Sat, 3 Dec 2016, Niels Möller wrote:
>> Hmm, you changed the code to not only allow G to be NULL, but allow NULL
>> S too?
> That was already the case before my patch.
Sorry for the confusin, I had forgotten it was your change.
> Since s and t may get swapped depending on the values of a and b, you
> cannot really support t==NULL without supporting s==NULL. You may
> prefer not documenting it though...
I think that's an implementation detail that shouldn't be documented.
Can we just strike it from the docs? (And possibly back it up with an
ASSERT at function entry).
In the case
mpn_gcdext(G, S, NULL, A, B)
with size(A) < size(B), IIRC we currently handle that by swapping
arguments, calling mpn_gcdext to compute T (even though the caller
didn't need that, and produce S with an multiplication using multiply +
That doesn't seem ideal. The alternative would be to do an up-front
division, and call mpn_gcdext with inputs A, B mod A, and some different
postprocessing (I don't have the cofactor stuff in my head at the
moment, it should be somewhere between easy and trivial, and likely
involving the quotient floor (B/A).
One also needs to keep in mind that if |A| < |B|, then typically |T| <
|S| too. Which could influence algorithm choice if the size difference
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel