Short division of long integers

(with Paul Zimmermann)

Proceedings of the 20th IEEE Symposium on Computer Arithmetic (ARITH 20), Tuebingen, July 25-27, 2011, pages 7–14 (DOI).

Preprint (May 2011).

Abstract

We consider the problem of short division — i.e., approximate quotient — of multiple-precision integers. We present ready-to-be-implemented algorithms that yield an approximation of the quotient, with tight and rigorous error bounds. We exhibit speedups of up to 30% with respect to GMP division with remainder, and up to 10% with respect to GMP short division, with room for further improvements. This work enables one to implement fast correctly rounded division routines in multiple-precision software tools.


Back to the main page