Short Division of Long Integers

David Harvey Paul Zimmermann 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We consider the problem of short division --- division without remainder --- 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.
Type de document :
Communication dans un congrès
Elisardo Antelo and David Hough and Paolo Ienne. 20th IEEE Symposium on Computer Arithmetic (ARITH-20), Jul 2011, Tuebingen, Germany. IEEE, pp.7-14, 2011, <10.1109/ARITH.2011.11>
Liste complète des métadonnées

https://hal.inria.fr/inria-00612232
Contributeur : Paul Zimmermann <>
Soumis le : jeudi 28 juillet 2011 - 13:16:13
Dernière modification le : jeudi 22 septembre 2016 - 14:31:29

Identifiants

Collections

Citation

David Harvey, Paul Zimmermann. Short Division of Long Integers. Elisardo Antelo and David Hough and Paolo Ienne. 20th IEEE Symposium on Computer Arithmetic (ARITH-20), Jul 2011, Tuebingen, Germany. IEEE, pp.7-14, 2011, <10.1109/ARITH.2011.11>. <inria-00612232>

Partager

Métriques

Consultations de la notice

236