Ancient Egyptian Multiplication and Binary Math

The Ancient Egyptian multiplication algorithm—also known as Ethiopian peasant multiplication or the method of doubling and halving—is an ancient mathematical technique used to multiply two integers using only addition, doubling, and halving. While developed millennia before the formal definition of modern arithmetic systems, the method works by implicitly decomposing one of the factors into a sum of powers of two, mirroring the exact principles behind the binary number system used in modern digital computing.

How the Ancient Egyptian Algorithm Works

The algorithm requires creating two parallel columns of numbers. Suppose you want to multiply two integers, \(A\) and \(B\):

1. Initialize the columns: Write \(1\) at the top of the first column and the second number (\(B\)) at the top of the second column.
2. Successive doubling: Repeatedly double the numbers in both columns on subsequent rows until the value in the first column would exceed the first number (\(A\)).
3. Decomposition: Identify which values in the first column add up exactly to \(A\).
4. Summation: Add the corresponding values in the second column to obtain the final product.

Example: Calculating \(13 \times 25\)

To represent \(13\), select the rows corresponding to \(8\), \(4\), and \(1\) (\(8 + 4 + 1 = 13\)).

Next, sum the corresponding entries in the second column: \[200 + 100 + 25 = 325\]

Thus, \(13 \times 25 = 325\).

Implicit Binary Decomposition

The core mechanism that makes Egyptian multiplication work is binary representation. In base 2, every positive integer can be uniquely expressed as a sum of distinct powers of two (\(2^0, 2^1, 2^2, 2^3, \dots\)).

The first column of the Egyptian table is an explicit list of the powers of two:

\[1 = 2^0, \quad 2 = 2^1, \quad 4 = 2^2, \quad 8 = 2^3, \quad \dots\]

When choosing the values in the first column that sum to \(A\), the algorithm computes the binary representation of \(A\):

\[13_{10} = (1 \times 2^3) + (1 \times 2^2) + (0 \times 2^1) + (1 \times 2^0) = 1101_2\]

The second column computes the partial products by scaling \(B\) by these corresponding powers of two:

\[B \times 2^0, \quad B \times 2^1, \quad B \times 2^2, \quad B \times 2^3\]

By applying the distributive property of multiplication over addition, the entire product is represented as:

\[A \times B = (b_k 2^k + \dots + b_1 2^1 + b_0 2^0) \times B = b_k(2^k B) + \dots + b_0(2^0 B)\]

where each bit \(b_i\) is either \(0\) or \(1\).

Selecting rows corresponds to setting \(b_i = 1\), and omitting rows corresponds to \(b_i = 0\). By doubling and selectively summing terms, the Ancient Egyptian method effectively executes the exact “shift-and-add” multiplication routine implemented in modern arithmetic logic units (ALUs).