GMP used during 3 and a half years to solve MIT's LCS35
Marco Bodrato
bodrato at mail.dm.unipi.it
Wed May 1 06:57:29 UTC 2019
Ciao Paul,
Il Mer, 1 Maggio 2019 8:22 am, paul zimmermann ha scritto:
> Dear Marco,
>
>> On the other side
>> mpz_powm (a, a, 2^2048, n);
>> should be faster than 2048 times
>> mpz_mul(b,a,a);
>> mpz_mod(a,b,n);
>
> not sure, since the base-2^k exponentiation will not help in that case
I agree, but "REDC form" should help.
> (either sliding window or not), since it saves multiplications,
> and in this case we have squarings only.
> Moreover, the base-2^k exponentiation will precompute a^i for i < 2^k,
> which will give some small overhead.
That's why a few weeks ago on this same list I suggested:
"What about even sparser exponents? Should we use 2*popcount(n) instead of
size_in_bits(n) to estimate the best window size? They should be almost
equivalent on average."
[ https://gmplib.org/list-archives/gmp-discuss/2019-April/006310.html ]
If we'd use popcount(n) to choose the "k" for "base-2^k", the
squaring-only cases like this one would not pre-compute any "a^i".
Ĝis,
m
--
http://bodrato.it/papers/
More information about the gmp-discuss
mailing list