## 12.2 INTEGERS

### 12.2.1 *B*'s Complement Multipliers

A straightforward implementation of Algorithm 5.7 (Section 5.3.1.1: mod *B*^{n+m} B's complement multiplication) consists of extending the representation of *X* and *Y* to *n + m* digits and computing the *n + m* less significant digits of *R*(*Z*) = *R*(*X*).*R*(*Y*). For that purpose any natural-number multiplier can be used. As an example, assume that a carry-save multiplier is used (Figure 12.5). The adder, ripple-carry, or whatever is no longer necessary as the *n + m* most significant digits must be truncated. So the array is limited to the rightmost *n + m* columns of the array represented in Figure 12.5. The cost and computation time of the obtained array are

where *C*_{2} and *T*_{2} are the cost and propagation time of the cell of Figure 12.3.

If *m = n*, then *C*(*n*) = *n*.(2.*n* + 1).*C*_{2}, and *T*(*n*, *m*) = 2.*n.T*_{2}. The computation time is the same as in the case of the natural numbers (12.3) but the cost is almost twice the cost *C*_{CSM} = *n*.(*n* + 1).*C*_{2} given by formula (12.4).

Another option is to implement Algorithm 5.8. A circuit similar to the ripple-carry multiplier of Figure 12.4 can be used. Every cell of the last row (Figure 12.3 with *i = n* − 1) must be replaced by a different one whose behavior is defined by the following rules:

**if** x_{n-1} = 0 **then**
**for** j **in** 0…m-1 **loop**
P_{n(n−1+j)} =P _{(n−1)(n−1+j)}; c_{(n−1)(j+1)}=0;
**endloop;**
**else**
c_{(n−1)1}=(c_{(n−1)j} +P_{(n−1)(n−1 + j)} + B-y_{0})/B;
P