Skip to Main content Skip to Navigation

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 : The multiplication by a constant problem consists in generating code to perform a multiplication by an integer constant, using elementary operations, such as left shifts (multiplications by powers of two), additions and subtractions. This can also be seen as a method to compress (or more generally encode) integers. We will not discuss about the quality of this compression method, but this idea will be used to find lower bounds on the code length (number of elementary operations).
Document type :
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:46:36 PM
Last modification on : Thursday, January 11, 2018 - 6:20:00 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:52:55 PM


  • HAL Id : inria-00072095, version 1



Vincent Lefèvre. Multiplication by an Integer Constant: Lower Bounds on the Code Length. [Research Report] RR-4493, INRIA. 2002, pp.15. ⟨inria-00072095⟩



Record views


Files downloads