5
$\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$
4
$\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$
  • $\begingroup$ That was helpful. I wrote the rest of a proof as another answer to this question. $\endgroup$ – Joseph Dasenbrock Jan 16 '17 at 17:20
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.