6
$\begingroup$

I'm studying a combinatorics text (Cameron) in preparation for taking discrete math this upcoming semester. I've taken a fair amount of math in college, through Calculus II, but this is my first 500+ level math course.

In chapter 2 of the Cameron book, the author introduces an algorithm for multiplication called Russian Peasant Multiplication. I want to prove that this algorithm will always result in the product of two numbers.

I've been chewing on the proof for a while now, and just can't seem to get any traction. Thanks in advance for any help.

Description of Algorithm

I'll try to explain the algorithm clearly. The goal of the algorithm is to find the product of two numbers $m$ and $n$. The below table is filled out for $m$ and $n$:

$$\begin{array}{c} m&&n&\\ \hline \bigl\lfloor \frac{m}{2} \bigr\rfloor&& 2n \\ \bigl\lfloor \frac{m}{4} \bigr\rfloor&& 4n \\ \bigl\lfloor \frac{m}{8} \bigr\rfloor&& 8n \\ \bigl\lfloor \frac{m}{16} \bigr\rfloor&& 16n \\ \bigl\lfloor \frac{m}{32} \bigr\rfloor&& 32n \\ \end{array}$$

The sequence of numbers in both columns is the sequence $a_n = 2a_{n-1}\text{ where }a_1=2$. The columns are extended down until the value in the left column is equal to the number one. After filling out the table, the product is found by adding the values of the right column where the left column is an odd number.

For example, to multiply 18 and 37 with the algorithm:

$$\begin{array}{c} m&&n&\\ \hline 18 && 37 \\ 9 && 74 \\ 4 && 148 \\ 2 && 296 \\ 1 && 592 \\ \end{array}$$

To find the product, cross out values of the left column where the value of the right column is even:

$$\begin{array}{c} m&&n&\\ \hline \require{enclose} \enclose{horizontalstrike}{18} && \enclose{horizontalstrike}{37} \\ 9 && 74 \\ \enclose{horizontalstrike}{4} && \enclose{horizontalstrike}{148} \\ \enclose{horizontalstrike}{2} && \enclose{horizontalstrike}{296} \\ 1 && 592 \\ \end{array}$$

And add the remaining numbers in the right column to get the result: $18\times37=74+592=666$

Alternate Description of Algorithm

As an aside, here is a shorter way to describe the algorithm, repeat the below steps until the left column == 1:

• Halve the last number in the first column
• Write the result below (discard the remainder)
• Double the last number in the first column.
• Write the result below.

Now, for every even number in the first column, delete the adjacent number in the second column. Add the remaining numbers in the second column.

What I've done so Far

I haven't been able to get much of anywhere on the proof. One thing I did was create a bit of a different way of arriving at the same outcome:

$$\begin{array}{c} m&&n&&\text{index}&&\text{remainder}&&\text{if remainder == 1, }n\times2^{Index}&\\ \hline 18 && 37 && 0 && 0 \\ 9 && 74 && 1 && 1 && 74\\ 4 && 148 && 2 && 0 \\ 2 && 296 && 3 && 0 \\ 1 && 592 && 4 && 1 && 592\\ \end{array}$$

Which brings to light the relationship between this algorithm and binary numbers (the fourth column in the above table is the product in binary, read bottom to top).

I also wrote some Python functions to help me explore the problem, Github repo.

$\endgroup$

3 Answers 3

5
$\begingroup$

Write $m$ in binary. The lines where the number is odd corresponds to the bits that are $1$ in the binary expansion. In your example of $18 \times 37$ we have $18=10010_2=2^1+2^4,$ so $18 \times 37=(2+16) \times 37$, which are exactly the terms you added.

$\endgroup$
1
  • $\begingroup$ That was helpful. I wrote the rest of a proof as another answer to this question. $\endgroup$
    – quantif
    Jan 16, 2017 at 17:20
2
$\begingroup$

After reading Ross Millikan's reply I decided to write a complete proof. This is my attempt:

A binary number is a way of expressing a number in powers of two, taking the form:

$$m = d_n2^{n-1}+d_{n-1}2^{n-2}+d_{n-2}2^{n-3}+...+d_{1}2^{0}$$

Where $n$ is the number of digits in the binary number. Therefore:

$$m\times n = \left[d_n2^{n-1}+d_{n-1}2^{n-2}+d_{n-2}2^{n-3}+...+d_{1}2^{0}\right]\times n$$

For example:

$$=18\times 37$$ $$\quad\;\;\;\;= \left[2^4+2\right]\times 37$$ $$\quad\;\;\;= \left[16+2\right]\times 37$$ $$\;= 592+74$$ $$666$$

The below table is a way of using this identity to multiply two numbers $m$ and $n$:

$$\begin{array}{c} \text{Index}&&m&&\text{If col. 1 is odd, }n\times 2^{Index}&\\ \hline 0 && m\\ 1 && \bigl\lfloor \frac{m}{2} \bigr\rfloor\\ 2 && \bigl\lfloor \frac{m}{4} \bigr\rfloor\\ 3 && \bigl\lfloor \frac{m}{8} \bigr\rfloor\\ 4 && \bigl\lfloor \frac{m}{16} \bigr\rfloor\\ 5 && \bigl\lfloor \frac{m}{32} \bigr\rfloor\\ \end{array}$$

Where the first column is the sequence of integers, the denominator in the second column is the sequence $a_n = 2a_{n-1}\text{ where }a_1=2$. The summation of the third column is the product $m\times n$.

Which is equivalent to these steps: repeat the below steps until the left column == 1:

• Halve the last number in the first column
• Write the result below (discard the remainder)
• Double the last number in the first column.
• Write the result below.

Now, for every even number in the first column, delete the adjacent number in the second column. Add the remaining numbers in the second column.

$\endgroup$
1
$\begingroup$

I'd like to add an answer to the already good ones just to point out that no explicit mention of binary representations is needed to understand the algorithm, yet every explanation I've found online mentions binary. When I first figured out how the algorithm works this didn't even occur to me! The idea is really simple:

$$18\times 37=9\times 74$$ Nothing surprising here, we just multiplied by $1$ in the form $2\times 1/2$. Since $18$ is even and no fractions come into play, we've just converted the original product into a new one and can discard the top row. Now we do the same halving/doubling again: $$9\times 74=(4+1/2)\times 148=4\times 148+1/2\times 148$$ And what's the last term? It's $74$, right above the $148$, which is next to the odd number $9$. Knowing that this will be accounted for at the end, ignore it for now and halve/double again with the remaining term: $$4\times 148=2\times 296$$ The $4\times 148$ row can be ignored. Continuing, $$2\times 296=1\times 592$$ Putting everything together, we end up with $18\times 37=592+74$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .