[Request for comments] Potential room for speedup when calculating divmod() of bases with many trailing 0 bits (in binary)
shlomif at gmail.com
Mon Sep 14 16:50:11 UTC 2020
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
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