Multiplication by Halving

Definition Russian peasant multiplication finds the product $mb$ of a nonnegative whole number $m$ and a whole number $b$. Write $m$ and $b$ as the first row of a two-column table. To make each new row, halve the left entry and discard any fractional part, so that 13 becomes 6, and double the right entry. Stop after the row whose left entry is 1. Then cross out every row whose left entry is even, and add the right entries of the rows that remain, the rows whose left entry is odd. The sum equals $mb$ for every such $m$ and $b$. When $m = 0$ no row has left entry 1, and the table is the single row with entries 0 and $b$. That row is crossed out, so nothing is added and the product is 0. The halved number must be a nonnegative whole number. The doubled number may be any number, because the method only doubles it and adds, and a product with a negative first factor is found by multiplying the absolute value of that factor by $b$ and changing the sign of the result.

Definition Halving and doubling rest on two identities, which hold for every whole number $k \ge 0$ and every number $b$.

Halving here is integer halving. A whole number $L \ge 0$ is either even, $L = 2k$, or odd, $L = 2k + 1$, and in both cases its integer half is $k = \lfloor L/2 \rfloor$, where $\lfloor x \rfloor$ is the largest whole number not exceeding $x$. Let $S$ be the sum of the right entries kept so far. One step of the method goes from a row with entries $L$ and $R$ to the row with entries $\lfloor L/2 \rfloor$ and $2R$, first adding $R$ to $S$ when $L$ is odd. By the identities the quantity $S + LR$ is an invariant, a quantity that is the same after every step. It starts as $0 + mb$. Each step makes a positive left entry smaller, so the left entry eventually becomes 0, one step after the row with left entry 1, and at that point $S + 0 \cdot R = S$. Hence the kept entries add up to exactly $mb$.

Definition The powers of two are the numbers $2^j$ for whole numbers $j \ge 0$, namely 1, 2, 4, 8, 16, 32 and so on, where $2^0 = 1$ and each power is twice the one before. For every $j \ge 1$ the powers below $2^j$ add up to one less than it,

In the multiplication table for $m$ and $b$, the row numbered $j$, counting the first row as row 0, holds $\lfloor m/2^j \rfloor$ on the left and $2^j b$ on the right. For $m \ge 1$ the table has $J + 1$ rows, where $2^J$ is the largest power of two not exceeding $m$.

Definition Every positive whole number $m$ can be written in exactly one way as a sum of distinct powers of two. Taking the largest power that does not exceed $m$ and repeating with what is left produces such a sum. That largest power must appear in every such sum for $m$, because all smaller powers together add up to 1 less than it, and repeating this argument with what is left shows that the sum is unique. The binary representation of $m$ lists, from the largest power used down to $2^0$, the digit 1 for each power in the sum and 0 for each power not in it. The number 0 is written 0. Integer halving reads these digits from the right. A whole number is odd exactly when its last binary digit is 1, and halving with the fractional part discarded deletes the last binary digit. So in the multiplication table the left entry of row $j$ is odd exactly when binary digit $j$ of $m$, counted from the right starting at 0, is 1. The kept rows therefore hold $2^j b$ for exactly the powers $2^j$ that make up $m$, and they add up to $mb$.

Definition Ancient Egyptian multiplication finds the product $mb$ for a positive whole number $m$ by doubling alone. Make a table whose rows are 1 and $b$, then 2 and $2b$, then 4 and $4b$ and so on, doubling both entries each time, and stop at the last row whose left entry does not exceed $m$. Then mark the rows whose left entries add up to exactly $m$, using each row at most once. Working from the last row up, mark a row whenever its left entry is no more than what is still needed, and subtract it. The marked rows are the powers of two in the binary representation of $m$, so the marked right entries add up to $mb$. They are the same right entries that Russian peasant multiplication keeps, found from the other end. The method appears in the Rhind papyrus, an Egyptian mathematical text from about 1550 BC.