Multiplication by Integer Constants

Abstract

Some modern machines have no integer multiple instruction and must rely on expensive software methods to compute integer products. In other cases, the multiply instruction is significantly slower than simple integer addition. When faced with computing n*c, where n is some unknown integer value and c is a known integer constant, we can avoid the need for a general-purpose multiply by rewriting the expression in terms of shifts, adds, and subtracts—typically all one-cycle instructions. Bernstein gives a detailed discussion of the problem and presents a solution, including Ada code for its implementation. Unfortunately, the code is flawed, at least in part due to typesetting errors. It's also quite difficult to understand. This document represents an attempt to explain the elements of Bernstein's approach. At the same time, we will develop a complete, working, and hopefully understandable implementation of his approach.