speed of unbalanced division
Zimmermann Paul
Paul.Zimmermann at loria.fr
Thu Feb 7 10:51:36 CET 2013
Torbjörn,
> You might want to try this patch. It removes lots of code, originally
> put in place for saving memory. It allows the divappr function to do
> its job more smoothly.
this is much better with this patch. Before I got:
frite% ./bug2 2000001 1000001
mpz_tdiv_q(2000001,1000001) took 1432ms
frite% ./bug2 1698971 698971
mpz_tdiv_q(1698971,698971) took 1816ms
Now I get:
frite% ./bug2 2000001 1000001
mpz_tdiv_q(2000001,1000001) took 1428ms
frite% ./bug2 1698971 698971
mpz_tdiv_q(1698971,698971) took 1352ms
We thus get a 26% speedup in the unbalanced case.
There are still some irregularities (cf 1500000 500000 below) but it is much
better than before:
frite% ./bug2 2000000 1000000
mpz_tdiv_q(2000000,1000000) took 1448ms
frite% ./bug2 1900000 900000
mpz_tdiv_q(1900000,900000) took 1420ms
frite% ./bug2 1800000 800000
mpz_tdiv_q(1800000,800000) took 1436ms
frite% ./bug2 1700000 700000
mpz_tdiv_q(1700000,700000) took 1372ms
frite% ./bug2 1600000 600000
mpz_tdiv_q(1600000,600000) took 1360ms
frite% ./bug2 1500000 500000
mpz_tdiv_q(1500000,500000) took 1456ms
frite% ./bug2 1400000 400000
mpz_tdiv_q(1400000,400000) took 1364ms
frite% ./bug2 1300000 300000
mpz_tdiv_q(1300000,300000) took 1080ms
frite% ./bug2 1200000 200000
mpz_tdiv_q(1200000,200000) took 1128ms
frite% ./bug2 1100000 100000
mpz_tdiv_q(1100000,100000) took 888ms
It would be interesting to recompute the graphs at http://gmplib.org/devel/
with that patch.
Paul
More information about the gmp-devel
mailing list