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

[Marco Bodrato]

Ciao,

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.

Ĝis,
m

-- 
http://bodrato.it/papers/