## 5.1 NATURAL NUMBERS MULTIPLICATION

### 5.1.1 Introduction

The most basic multiplication algorithms for *n*-digit × *m*-digit *B*-ary natural numbers (shift and add algorithms) proceed in two phases:

- Digitwise partial products (
*n* × *m*),
*Multioperand* addition.

The classic computation scheme to introduce multiplication is given in Figure 5.1a, where partial products appear lined up according to their respective weight. This scheme is historically related to the pencil and paper implementation of the operation. This simple scheme is easily built up by noting that the partial products *x*_{i} y_{j} are lined up in the column whose index *k* = *i* + *j* corresponds to the weight *B*^{k}. Observe that whenever *B* > 2, the partial products may need two base-*B* digits. For *B* > 2, a possible multiplication scheme is displayed at Figure 5.1b, where *X*_{i}Y_{j} and *x*_{i}y_{j} stand, respectively, for the integer product

and the mod B product

Observe that the column index *k* remains *i* + *j* for products (5.2) but is computed as *i* + *j* + 1 for products (5.1).

**Figure 5.1** (a) Multiplication scheme and (b) multiplication scheme for *B* > 2.

The cost/speed constraints are key factors to set trade-offs between combinational parallel schemes and sequential ...