Skip to Main content Skip to Navigation

Software Carry-Save for Fast Multiple-Precision Algorithms

Abstract : This paper introduces a new machine representations of multiple-precision (MP) numbers, geared toward simple and fast implementations. We observe, in the usual high-radix representations, that carry management accounts for a lot of the complexity of the core multiple-precision algorithms (addition and multiplication). Our representation therefore trades space for simplicity : the digits of the multiple-precision numbers are coded on less bits than the machine numbers can offer. The reserved bits are used during MP addition and multiplication to guarantee that no overflow or rounding can occur in any internal computations. This leads to simple and therefore fast algorithms. In other words, all the carries generated in these internal computations are saved in these reserved bits, to be managed as late as possible. In addition to simplicity, this \emph{software carry-save representation} allows to expose parallelism just like its hardware counterpart. An initial implementation of this representation is shown to compare favorably to other multiple-precision libraries.
Document type :
Complete list of metadatas
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:36 AM
Last modification on : Wednesday, July 8, 2020 - 12:43:29 PM


Files produced by the author(s)


  • HAL Id : hal-02102038, version 1



David Defour, Florent de Dinechin. Software Carry-Save for Fast Multiple-Precision Algorithms. [Research Report] LIP RR-2002-08, Laboratoire de l'informatique du parallélisme. 2002, 2+10p. ⟨hal-02102038⟩



Record views


Files downloads