Multiplication by a Constant is Sublinear

Vassil Dimitrov Laurent Imbert 1 Andrew Zakaluzny
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper explores the use of the double-base number system (DBNS) for constant integer multiplication. The DBNS recoding scheme represents integers – in this case constants – in a multiple-radix way in the hope of minimizing the number of additions to be performed during constant multiplication. On the theoretical side, we propose a formal proof which shows that our recoding technique diminishes the number of additions in a sublinear way. Therefore, we prove Lefèvre's conjecture that the multiplication by an integer constant is achievable in sublinear time. In a second part, we investigate various strategies and we provide numerical data showcasing the potential interest of our approach.
Type de document :
Communication dans un congrès
ARITH-18: 18th IEEE Symposium on Computer Arithmetic, Jun 2007, Montpellier, France, IEEE Computer Society, pp.261-268, 2007
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00158322
Contributeur : Laurent Imbert <>
Soumis le : jeudi 28 juin 2007 - 15:09:22
Dernière modification le : mardi 11 décembre 2018 - 17:16:02

Identifiants

  • HAL Id : lirmm-00158322, version 1

Collections

Citation

Vassil Dimitrov, Laurent Imbert, Andrew Zakaluzny. Multiplication by a Constant is Sublinear. ARITH-18: 18th IEEE Symposium on Computer Arithmetic, Jun 2007, Montpellier, France, IEEE Computer Society, pp.261-268, 2007. 〈lirmm-00158322〉

Partager

Métriques

Consultations de la notice

64