Sublinear constant multiplication algorithms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2006

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

Dates and versions

lirmm-00135824 , version 1 (09-03-2007)

Identifiers

Cite

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⟩
89 View
0 Download

Altmetric

Share

More