Sublinear constant multiplication algorithms

Vassil Dimitrov 1 Laurent Imbert 2 Andrew Zakaluzny 1
1 ECE-Calgary - Dept. of Electr. and Comp. Eng.
2 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper explores the use of a double-base number system (DBNS) in constant integer multiplication. The DBNS recoding technique represents constants in a multiple-radix way in the hopes of minimizing computation during constant multiplication. The paper presents a proof to show that multiple-radix representation diminishes the number of additions in a sublinear way. We prove Lefevre's conjecture that the multiplication by an integer constant is achievable in sublinear time. The proof is based on some interesting properties of the double-base number system. The paper provides numerical data showcasing some of the most recent results.
Document type :
Conference papers
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00135824
Contributor : Laurent Imbert <>
Submitted on : Friday, March 9, 2007 - 9:20:30 AM
Last modification on : Wednesday, October 9, 2019 - 9:42:02 AM

Identifiers

Collections

CNRS | ARITH | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Vassil Dimitrov, Laurent Imbert, Andrew Zakaluzny. Sublinear constant multiplication algorithms. Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 2006, San Diego, CA, United States. pp.631305, ⟨10.1117/12.680289⟩. ⟨lirmm-00135824⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

95

Contact

Informations

CCSD