[Request for comments] Potential room for speedup when calculating divmod() of bases with many trailing 0 bits (in binary)

[Shlomi Fish]

Hi Marco!

On Wed, Sep 23, 2020 at 9:14 PM Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> Il 2020-09-23 09:05 Shlomi Fish ha scritto:
> > The results are similar to the previous ones:
>
> > ~/progs/python/shift_divmod/gmp-shift_divmod/ time pypy3
>
> > 23.35s user 0.04s system 99% cpu 23.495 total
>
> > ./pure-gmp-bench.exe  29.09s user 0.01s system 99% cpu 29.161 total
>
> Probably, the pypy3 optimiser uses 23 seconds to understand that your
> mytest function is computing: ((2^(2^1000-p)%p)<<p)%(p*p)/p, and uses
> the remaining 0.35 seconds to compute it :-)
> But I'm sure that a well written GMP sequence using powm can compute
> that formula in less than 0.01 seconds :-D
>
> I'm obviously joking. I do not know anything about pypy internals.
> I can not help you here.
>

I see, heh. I have some code with gmp powm for the original use case
and it is indeed fast. Regarding the benchmark: I think 29s of runtime
instead of 23s is acceptable but the 160s that it takes gmplib without
your patch (or my wrapper code) is less so.


-- 
Shlomi Fish https://www.shlomifish.org/

Buddha has the Chuck Norris nature.

Please reply to list if it's a mailing list post - http://shlom.in/reply .