Sublinear constant multiplication algorithms

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, 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 11 janvier 2018 - 06:26:07

Identifiants

Collections

Citation

Vassil Dimitrov, Laurent Imbert, Andrew Zakaluzny. Sublinear constant multiplication algorithms. Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 2006, SPIE, 6313, pp.631305, 2006, Proceedings of SPIE. 〈10.1117/12.680289〉. 〈lirmm-00135824〉

Partager

Métriques

Consultations de la notice

26