Paul Erd?s Multiplication Algorithm – How It Works

algorithmselementary-number-theory

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.

Best Answer

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

Related Question