A straightforward implementation of Algorithm 5.7 (Section 188.8.131.52: mod Bn+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 C2 and T2 are the cost and propagation time of the cell of Figure 12.3.
If m = n, then C(n) = n.(2.n + 1).C2, and T(n, m) = 2.n.T2. The computation time is the same as in the case of the natural numbers (12.3) but the cost is almost twice the cost CCSM = n.(n + 1).C2 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: