Multiplication by a Constant is Sublinear - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2007

Multiplication by a Constant is Sublinear

Vassil Dimitrov
  • Function : Author
Laurent Imbert
Andrew Zakaluzny
  • Function : Author

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.
No file

Dates and versions

lirmm-00158322 , version 1 (28-06-2007)

Identifiers

  • HAL Id : lirmm-00158322 , version 1

Cite

Vassil Dimitrov, Laurent Imbert, Andrew Zakaluzny. Multiplication by a Constant is Sublinear. ARITH-18: 18th IEEE Symposium on Computer Arithmetic, Jun 2007, Montpellier, France, pp.261-268. ⟨lirmm-00158322⟩
115 View
0 Download

Share

More