Multiplication by an Integer Constant: Lower Bounds on the Code Length

Vincent Lefèvre 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we deal with code that performs a multiplication by a given integer constant using elementary operations, such as left shifts (i.e. multiplications by powers of two), additions and subtractions. Generating such a code can also be seen as a method to compress (or more generally encode) integers. We will discuss neither the way of generating code, nor the quality of this compression method, but this idea will here be used to find lower bounds on the code length, i.e. on the number of elementary operations. || Dans ce papier, nous parlons de code pour effectuer une multiplication par un entier donné à l'aide d'opérations élémentaires, comme des décalages vers la gauche (i.e. des multiplications par des puissances de deux), des additions et des soustractions. Gé
Type de document :
Communication dans un congrès
5th Conference on Real Numbers and Computers 2003 - RNC5, 2003, Lyon, France, pp.131-146, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00099684
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:40:19
Dernière modification le : vendredi 29 septembre 2017 - 13:44:07

Identifiants

  • HAL Id : inria-00099684, version 1

Collections

Citation

Vincent Lefèvre. Multiplication by an Integer Constant: Lower Bounds on the Code Length. 5th Conference on Real Numbers and Computers 2003 - RNC5, 2003, Lyon, France, pp.131-146, 2003. 〈inria-00099684〉

Partager

Métriques

Consultations de la notice

68