mpz reuse test takes too much time

[Marco Bodrato]

Ciao,

Il Dom, 1 Gennaio 2017 9:03 pm, Niels Möller ha scritto:
> nisse at lysator.liu.se (Niels Möller) writes:
>
>> 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 +
>> exact division.
>
> I've looked a bit more at this, and it's not at clear to me what
> strategy one should use.

> Now we have two possible strategies:
>
> 1. Call mpn_gcdext (B, A), which produces T. And compute S as
>
>      S = (G - T B) / A

This means computing both cofactors, right?

> 2. First do a division up front,
>
>      B = Q A + R
>
>    and call mpn_gcdext(A, R). We then get a cofactor S', of m limbs. But
>    we also need the other cofactor T', because the wanted cofactor S is

This also means computing both cofactors, don't it?

I assume that the best way to compute both cofactors is the one currently
implemented in mpz_gcdext. If it is not, than we should rewrite mpz_gcdext
from scratch, not just trying to optimise the only-S-wanted case...

> And a third strategy could be to extend mpn_gcdext to support A < B, and
> hence compute the larger cofactor directly. But I'd guess that would be
> more work, since gcdext uses a quadratic algorithm for much larger sizes
> than for multiplication and division.

Actually mpn_gcdext supports A<B, but it requires to zero-pad A so that
its length in limbs is not smaller than the length of B.

It is supported because internally mpn_gcdext (A,B) computes at first A'=A
(mod B) then continues as if the operands was (A',B)... (going back to the
"2. First do a division" proposal, we should also compute the extra-cost
of the division+reminder algorithm compared to the remainder-only used by
mpn_gcdext).

I tested this strategy with the code proposed in another thread
https://gmplib.org/list-archives/gmp-devel/2016-December/004492.html but
I'm not convinced by the results...

Best regards,
m

-- 
http://bodrato.it/