short division

[Zimmermann Paul]

       Hi,

together with David Harvey, we have written a paper on short division, which
compares two approaches : (1) Mulders' short division algorithm and (2)
Barrett's l-fold division [3].

On our target architecture, both approaches give comparable results, with a
performance which is about 10% better than GMP's mpn_div_q function, which
was introduced in GMP 5, and computes quotient only (note that our functions
compute an *approximate* quotient only, however for MPFR in most cases it is
sufficient).

The first short division algorithm is already available in the MPFR svn
repository, and should be used in the next MPFR major release. As a consequence
MPFR division should be again faster than GMP floating-point division [1,2].
The other division algorithm is not yet available in MPFR, since it relies on
Harvey's middle product, which is itself not yet available in GMP. In addition
the paper gives rigorous bounds for Mulders' short multiplication, which is
used since MPFR 2.2.0.

Paul Zimmermann

[1] http://www.mpfr.org/mpfr-2.4.0/timings.html
[2] http://www.mpfr.org/mpfr-3.0.0/timings.html
[3] http://www.loria.fr/~zimmerma/papers/div-final.pdf