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

Shlomi Fish shlomif at gmail.com
Mon Sep 14 16:50:11 UTC 2020

Hi all!

I was able to improve upon mpz_mod here:


This is in case the number that one divides by is itself divisible by a
large power of 2.

The benchmarks are:


With the C and gmplib version:

   - mpz_mod runs the benchmark in about 160 seconds.
   - shift_divmod runs the benchmark in about 35 seconds.
   - pypy3 runs the pure-Python code in 25 seconds (!).


Code is free & open source under MITL/ExpatL but note that running the
tests requires cmocka ( https://cmocka.org/ ) and my own librinutils (
https://github.com/shlomif/rinutils ) and I haven't set up CI for that
repository yet.

Is there interest in incorporating such a change to the core GMP library?

Regards, -- Shlomi

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 .

More information about the gmp-discuss mailing list