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, Laurent Imbert, 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