speed of unbalanced division

[Zimmermann Paul]

       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