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

Solution 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$.

Solution 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)$.

Solution 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.

Solution 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!