Software Carry-Save for Fast Multiple-Precision Algorithms - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2002

Software Carry-Save for Fast Multiple-Precision Algorithms


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.
Fichier principal
Vignette du fichier
RR2002-08.pdf (222.04 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102038 , version 1 (17-04-2019)


  • 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⟩
43 Consultations
349 Téléchargements


Gmail Facebook Twitter LinkedIn More