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

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072095
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

Identifiers

  • HAL Id : inria-00072095, version 1

Collections

Citation

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

Share

Metrics

Record views

147

Files downloads

161