25 August 2006 Sublinear constant multiplication algorithms
Author Affiliations +
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.
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Vassil Dimitrov, Vassil Dimitrov, Laurent Imbert, Laurent Imbert, Andrew Zakaluzny, Andrew Zakaluzny, } "Sublinear constant multiplication algorithms", Proc. SPIE 6313, Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 631305 (25 August 2006); doi: 10.1117/12.680289; https://doi.org/10.1117/12.680289

Back to Top