TABLE OF CONTENTS This chapter presents the basic sequential algorithms for multiplication, division, and square root extraction. Algorithms for high-speed multiplication are described in Chapter 6. Chapters 7, and 8 include algorithms for fast division and high-speed calculation of square roots.
Let the multiplier and multiplicand be denoted by X and A, respectively, with the following sequences of digits:
where x n ?1 and a n ?1 are the sign digits in either the signed-magnitude or the complement methods.
The sequential algorithm for multiplication consists of n ?1 steps where in step j the multiplier bit x j is examined and the product x j A is added to the previously accumulated partial product, denoted by P (j). The appropriate expression for this recursive procedure is
where in the first step p (0)=0. Multiplying the sum (p (j) +x j A) by 2 ? 1 shifts it by one position to the right, to align p ( j +1) before adding the next product x j +1 A. This alignment is necessary, since the weight of x j +1 is double that of x j. To prove that the above procedure calculates the product of A and X, we repeatedly substitute into the recursive Equation (3.1), yielding
If both operands are positive (i.e., x n ?1= a n ?1=0), the product U is obtained from
The result is a...
