Multiplication Algorithms

Historical roots of algorithms

Although they have been a topic of formal academic study for only a few decades, algorithms have been with us since the dawn of civilization. Descriptions of step-by-step arithmetic computation are among the earliest examples of written human language, long predating the expositions by Fibonacci and al-Khwarizmi, or even the place value notation they popularized.

Lattice multiplication

The most familiar method for multiplying large numbers, at least for American students, is the lattice algorithm. This algorithm was popularized in Liber Abaci by Fibonacci, who learned it from Arabic sources including al-Khwarizmi, who in turn learned it from Indian sources including the 7th century treatise Brahmasphutasiddhanta by Brahmagupta, who may have learned it in turn from Chinese sources. The oldest surviving descriptions of the algorithm appear in The Mathematical Classic of Sunzi, written in China between the 3rd and 5th centuries, and in Eutocius of Ascalon’s commentaries on Archimedes’ Measurement of the Circle, written around 500CE. However, there is evidence that the algorithm was known much earlier. Eutocius credits the method to a lost treatise of Apollonius of Perga, who lived around 300BCE, entitled Okytokion ($`$$\Omega$$\kappa$$\vartheta$$\tau$$\acute{o}$$\kappa$$\iota$$o$$\nu$). The Sumerians recorded multiplication tables on clay tablets as early as 2600BCE, suggesting that they may have used the lattice algorithm.

The lattice algorithm assumes that the input numbers are represented as explicit strings of digits. Here, we’ll assume that we’re working in base ten, but the algorithm generalizes immediately to any other base. To simplify notation, the input consists of a pair of arrays $X [0 .. m − 1]$ and $Y [0 .. n − 1]$, representing the numbers

$$x = \sum_{i=0}^{m-1}X[i].10^i \text{\ \ and\ \ } y = \sum_{j=0}^{n-1}Y[j].10^j,$$

and similarly, the output consists of a single array $Z [0 .. m + n − 1]$, representing the product

$$z=x.y=\sum_{k=0}^{m+n-1}Z[k].10^k.$$

The algorithm uses addition and single-digit multiplication as primitive operations. Addition can be performed using a simple for loop. In practice, single-digit multiplication is performed using a lookup table, either carved into clay tablets, painted on strips of wood or bamboo, written on paper, stored in read-only memory, or memorized by the computator. The entire lattice algorithm can be summarized by the formula

$$x.y = \sum_{i=0}^{m-1}\sum_{j=0}^{n-1}(X[i].Y[j].10^{i+j})$$

Different variants of the lattice algorithm evaluate the partial products $X [i] · Y [ j] · 10^{i+ j}$ in different orders and use different strategies for computing their sum. For example, in Liber Abaci, Fibonacci describes a variant that considers the mn partial products in increasing order of significance, as shown in modern pseudocode below.