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 :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102038
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:36 AM
Last modification on : Wednesday, November 20, 2019 - 3:10:39 AM

File

RR2002-08.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102038, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

25

Files downloads

65