Sublinear constant multiplication algorithms

Vassil Dimitrov; Laurent Imbert; Andrew Zakaluzny

doi:10.1117/12.680289

25 August 2006 Sublinear constant multiplication algorithms

Vassil Dimitrov, Laurent Imbert, Andrew Zakaluzny

Proceedings Volume 6313, Advanced Signal Processing Algorithms, Architectures, and Implementations XVI; 631305 (2006) https://doi.org/10.1117/12.680289
Event: SPIE Optics + Photonics, 2006, San Diego, California, United States

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.

Citation Download Citation

Vassil Dimitrov, Laurent Imbert, and Andrew Zakaluzny "Sublinear constant multiplication algorithms", Proc. SPIE 6313, Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 631305 (25 August 2006); https://doi.org/10.1117/12.680289

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available