mpz reuse test takes too much time
Niels Möller
nisse at lysator.liu.se
Wed Jan 18 17:59:20 UTC 2017
"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
>> 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?
Yes.
>> 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 think you're right. We compute S' and T' (gcdext after initial
division), and then construct S. So I didn't say that we compute T. But
in fact, T' = T, since T = (B/G)^-1 (mod A/G), T' = (R/G)^-1 (mod A/G),
and B = R (mod A). Right?
> I assume that the best way to compute both cofactors is the one currently
> implemented in mpz_gcdext.
It's best under the theory think that a few large multiplications at the
end is more efficient than building up the other cofactor incrementally.
But might not be true in all cases...
But we should probably reorganize mpn_gcdexp first, before evaluating
other strategies regarding the larger cofactor. The divide-and-conquer
thing should be done slightly different, and that might make it
cheaper to get the other cofactor at least for large operands.
>> 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.
Maybe the way mpn_gcdext handles this can be more or less unchanged. But
we shouldn't have to zeropad the input.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list