mpz reuse test takes too much time
Marco Bodrato
bodrato at mail.dm.unipi.it
Tue Jan 10 22:05:34 UTC 2017
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/
More information about the gmp-devel
mailing list