Share Email Print
cover

Proceedings Paper

Sublinear constant multiplication algorithms
Author(s): Vassil Dimitrov; Laurent Imbert; Andrew Zakaluzny
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 25 August 2006
PDF: 9 pages
Proc. SPIE 6313, Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 631305 (25 August 2006); doi: 10.1117/12.680289
Show Author Affiliations
Vassil Dimitrov, ATIPS, CISaC, Univ. of Calgary (Canada)
Laurent Imbert, ATIPS, CISaC, Univ. of Calgary (Canada)
LIRMM, CNRS, Univ. Montpellier 2 (France)
Andrew Zakaluzny, ATIPS, CISaC, Univ. of Calgary (Canada)


Published in SPIE Proceedings Vol. 6313:
Advanced Signal Processing Algorithms, Architectures, and Implementations XVI
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top