A multiplication algorithm found in a book by Paul Erdős: how does it work?

Question

I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"):

We can multiply two (positive integer) numbers together in the following way. Write the two numbers down next to each other. Divide the first in half, rounding down to an integer, and write the result below it. Double the second number, writing the result below it. We continue this halving / doubling until we are left with $1$ in the first column. Cross out all those numbers in the second column that are opposite an even number and add the remaining numbers in this column together to get the product. Prove that this works.

And this is an example, $73 \cdot 217$:

$(73,217)$

$(36, 434)$

$(18, 868)$

$(9, 1736)$

$(4, 3472)$

$(2, 6944)$

$(1, 13888)$

Then $73 \cdot 217 = 217+1736+13888 = 15841$, which is correct.

... and I really cannot visualize the reason why it works. My thoughts so far:

• We are dividing by $2$ in the left column, so only those values that are odd are coming from a division of a previous even number in the left column, and that means that the previous division by $2$ was "perfect", meaning without decimals.

• I can approximate the value of the product of two natural numbers $p \cdot q$ if I divide the first number by $2$ continuously until it arrives at $1$ and multiply the second by $2$ at the same time (so the final value of the second one is an approximation of the product).

But why do we remove some of them for the final sum? I would like to ask the following questions:

1. How does it work?

2. We are summing the numbers of the second column that are opposite an odd number. Then what does the sum of the numbers that we do not use from the second column represent?

This is all probably pretty obvious, but I cannot see the light.

Answer 1

This method is often called "Russian peasant multiplication".

It's often justified by thinking about writing the first number in binary. Here's another way to explain it. At each step, we're replacing a pair $(p,q)$ either by $(\frac{p}{2}, 2q)$ (when $p$ is even) or by $(\frac{p-1}{2},2q)$ (when $p$ is odd).

• In the first case, when $p$ is even, the product of the two numbers doesn't change: $p \cdot q = \frac{p}{2} \cdot 2q$.
• In the second case, when $p$ is odd, $\frac{p-1}{2} \cdot 2q = p \cdot q - q$. So the product has decreased by $q$, and we should set $q$ aside for later.

Eventually, we get to a pair $(1,r)$ whose product is easy to compute: it's just $r$. Because we've kept track of how the product of a pair has changed, we know that the original product is equal to this product, plus all the numbers we've set aside.

But we set aside $q$ from the pair $(p,q)$ whenever $p$ is odd. So adding the numbers we set aside to the final number just corresponds to adding up the second number in every pair whose first number is odd.

---

You also wanted to know what the sum of the numbers opposite an even number represents.

Given a $p$ and $q$ you want to multiply, choose $k$ such that $2^{k-1} - 1 < p \le 2^k - 1$. (In other words, $2^k$ is the next power of $2$ after $p$, not including $p$ itself.)

Then if we use this algorithm to find $(2^k-1)\cdot q$, we'll take the same number of steps to get to $1$ on the left-hand side, but all the left-hand numbers along the way are odd. This tells us that the sum of all the right-hand numbers should be the product $(2^k-1) \cdot q$.

Since the sum of all the right-hand numbers opposite an odd left-hand number is $p \cdot q$, the sum of all the right-hand numbers opposite an even left-hand number is their difference $(2^k-1-p) \cdot q$.

Answer 2

Write $75$ in binary: $\mathtt{1001011}$; now write down a table starting from the rightmost digit (I use $75$ to avoid undesired symmetry): $$ \begin{array}{lrr} \mathtt{1}=a_0 & 75 & 217 \\ \mathtt{1}=a_1 & 37 & 434 \\ \mathtt{0}=a_2 & 18 & 868 \\ \mathtt{1}=a_3 & 9 & 1736 \\ \mathtt{0}=a_4 & 4 & 3472 \\ \mathtt{0}=a_5 & 2 & 6944 \\ \mathtt{1}=a_6 & 1 & 13888 \end{array} $$ As you can see, odd numbers in the center column correspond to a digit $\mathtt{1}$ in the binary representation. This is not by chance: removing the rightmost digit from the binary representation is exactly dividing by $2$ (discarding the remainder) and a rightmost digit $\mathtt{1}$ means the number is odd.

The factor $m=75$ is written $$ m=2^0a_0+2^1a_1+2^2a_2+2^3a_3+2^4a_4+2^5a_5+2^6a_6 $$ Therefore, if $n=217$, the product is \begin{align} mn&=(2^0a_0+2^1a_1+2^2a_2+2^3a_3+2^4a_4+2^5a_5+2^6a_6)n \\ &=2^0a_0n+2^1a_1n+2^2a_2n+2^3a_3n+2^4a_4n+2^5a_5n+2^6a_6n \\ &=\begin{aligned}[t] &a_0\cdot (2^0n)+{}\\ &a_1\cdot (2^1n)+{}\\ &a_2\cdot (2^2n)+{}\\ &a_3\cdot (2^3n)+{}\\ &a_4\cdot (2^4n)+{}\\ &a_5\cdot (2^5n)+{}\\ &a_6\cdot (2^6n) \end{aligned} \end{align} Each number in parentheses in the final sum (written in column) is twice the preceding one (starting from $n$). Now, using the explicit data, we get $$ \begin{array}{r@{}rl} 1\cdot{}&217 &+ \\ 1\cdot{}&434 &+ \\ 0\cdot{}&868 &+ \\ 1\cdot{}&1736 &+ \\ 0\cdot{}&3472 &+ \\ 0\cdot{}&6944 &+ \\ 1\cdot{}&13888 &=\\ \hline &217 &+ \\ &434 &+ \\ &1736 &+ \\ &13888 &=\\ \hline &16275 \end{array} $$

If you use all terms in the final column of the first table, you are multiplying $217$ by the binary number $\mathtt{1111111}=2^7-1=127$.

So the sum of the numbers opposite the even digit corresponds to the product $217\cdot(127-75)$.

Answer 3

Another way of putting it for anyone else who comes by and reads this:

At first you have a bunch of $217$s. $73$ of them. That's $73 \cdot 217$. You divide on one side and double on the other so the product remains the same.

But you have to round down when you halve $73$. So instead of saying $73 \cdot 217$ you say $72 \cdot 217 + 1 \cdot 217$. Then you can say you have $36 \cdot 434 + 1 \cdot 217$.

You "left behind" a $217$ when you rounded down. Likewise you also end up "leaving behind" the $1736$. So at the end, before you can say you're done, you have to go back and account for the numbers you left behind.

Answer 4

The binary aspect is a nice thing to mention, since this is very close to the actual implementation of a multiplier unit inside a CPU. This is how the 73*217 example would go:

            (a)                 (b)
         1001001             11011001 (added to result)
          100100            110110010 (ignored)
           10010           1101100100 (ignored) 
            1001          11011001000 (added to result)
             100         110110010000 (ignored) 
              10        1101100100000 (ignored) 
               1       11011001000000 (added to result)
                       --------------
                       11110111100001 (result)

If the least significant bit of a is 1 (this means a is odd) then we add b to the result. Then, we divide a by 2 (bit shift right) , multiply b by 2 (bit shift left) and loop.

Another way to view this is to picture it in the same way we write a multiplication on paper, in base 10: we multiply each digit of a by each digit of b separately, while handling the carries. In binary, digits are only 0 or 1, so it boils down to "add b" or "do not add b".

So, instead of dividing a by 2, we can examine the n-th digit of a in binary representation. Since the weight of each digit in a is 2^n, if the digit n is 1, we add b*2^n to the result.

            (a)                       (b)
         1001001                   11011001 (b * 2^0)
               ^ digit 0
         1001001                11011001000 (b * 2^3)
            ^ digit 3
         1001001             11011001000000 (b * 2^6)
         ^ digit 6
                             --------------
                             11110111100001 (result)

A very slow CPU will do this iteratively in software, using only bit-shift, bit test and addition instructions.

Example for Z80 CPU

A slightly faster CPU, like Cortex-M0 "light" will do this iteratively in hardware: you get a conditional adder wired to a bit-shifter. It will use up to 32 cycles for a 32bit x 32bit MUL, but of course multiplying by a smaller number could use less cycles.

And a fast CPU will implement the entire thing as a single circuit, which is usually also pipelined. It tends to be quite complicated and use a massive amount of logic, but that's how you get 1 MUL per clock cycle throughput.

So, that Russian Peasant was actually quite modern!

Answer 5

(Note by OP: as a complement to the answers, @ixi has kindly written a Python snippet that performs the Russian peasant algorithm)

def russian_peasant_multiplication(a,b, acc = 0):
    print(a,b,acc+b)
    if a == 1:
        return b + acc
    elif (a%2) == 0:
        return russian_peasant_multiplication(a//2,b*2,acc)
    else:
        return russian_peasant_multiplication(a//2,b*2,acc+b)
assert russian_peasant_multiplication(73, 217) == 15841