GMP used during 3 and a half years to solve MIT's LCS35

Marco Bodrato bodrato at
Mon Dec 16 16:17:45 UTC 2019


Il 2019-12-16 16:30 tg at ha scritto:
> paul zimmermann <Paul.Zimmermann at> writes:
>   thank you for the benchmark, which shows a clear gain with the 
> popcount
>   method when the exponent is sparse, and no regression when it is not.
> I believe that the amount of analysis of the exponent we can afford is 
> a
> function of the expected computation time.

I agree. For size n=1 the popcount method is often slower.

> A popcount adds linear time in the exponent size.  If the base and
> modular argument are small enough, that will add noticeable overhead.
> We might want to do a more sophisticated analysis of the exponent when
> the base and modular are are large enough.

I think we can look at the exponent only. The window size is based on 


More information about the gmp-devel mailing list