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.
Type de document :
Communication dans un congrès
Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 2006, San Diego, CA, United States. SPIE, 6313, pp.631305, 2006, Proceedings of SPIE. 〈10.1117/12.680289〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00135824
Contributeur : Laurent Imbert <>
Soumis le : vendredi 9 mars 2007 - 09:20:30
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Lien texte intégral

openaccess

Identifiants

Collections

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. SPIE, 6313, pp.631305, 2006, Proceedings of SPIE. 〈10.1117/12.680289〉. 〈lirmm-00135824〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

44

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD