Russian peasant multiplication and loop invariants

Russian peasant multiplication is a method for multiplying numbers based on repeated doubling and halving. Nobody is quite sure why it is called “Russian peasant multiplication,” but the name has stuck.

Here is the procedure:

  1. Write each number at the head of a column.
  2. Double the number in the first column.
  3. Halve the number in the second column. (If odd, ignore the remainder.)
  4. Repeat (2) and (3) until the number in the second column is 1.
  5. Cross out the rows with an even number in the second column.
  6. Add up the remaining numbers in the first column.

Example: Multiply 43 by 18.

First number Second number
 43   18 
\(86\) \(9\)
 172   4 
 344   2 
\(688\) \(1\)

\(\implies 43 \times 18 = 86 + 688 = 774.\)

Here is a Python implementation of the algorithm.

def multiply(m, n):
    p = 0
    while n > 0:
        if n % 2: # n is odd
            p = p + m
        m = m * 2
        n = n // 2
    return p

Correctness

Let’s see what happens to the values of \(m\), \(n\), and \(p\) in one iteration. If \(n\) is even, then \(m\) is doubled and \(n\) is halved, so the product \(mn\) is unchanged. If \(n\) is odd, then \(m\) is doubled and \(n\) is replaced with \((n-1)/2\), so the value of the product \(mn\) is decreased.
\[(2m) \cdot (n-1)/2 = mn – m\]
To compensate for this decrease, the value of \(p\) is increased by \(m\) when \(n\) is odd. Consequently, the value of \(Q = mn + p\) does not change – it is a loop invariant. At the beginning of the loop we have \(Q = mn\) (since \(p=0\)) and at the end we have \(Q = p\) (since \(n=0\)). Therefore, the product \(mn\) is equal to the final value of \(p\).

A decimal variation

The Russian Peasant method is associated with binary (base two) arithmetic, since it involves multiplying and dividing by two. Is there a decimal (base ten) version? Consider the following:

def multiply_decimal(m, n):
    p = 0
    while n > 0:
        r = n % 10
        p = p + m * r
        m = m * 10
        n = n // 10
    return p

Let’s analyze this algorithm. Each time through the loop, the values of \(m\), \(n\), and \(p\) are replaced with new values \(m’\), \(n’\), and \(p’\). The following relations hold between the new values and the old values.
\[
\begin{align*}
m’ &= 10m\\
n &= 10n’ + r\\
p’ &= p + mr
\end{align*}
\]

As before, the quantity \(Q = mn+p\) is a loop invariant, since
\(
mn + p = m(10n’ + r) + p = (10m)n’ + (p + mr) = m’n’ + p’.
\)
Therefore, the function returns the product \(mn\).

Example: Multiply 123 by 456.

\(m\) \(n\) \(mr\)
\(123\) \(456\) \(123 \times 6 = 738\)
\(1230\) \(45\) \(1230 \times 5 = 6150\)
\(12300\) \(4\) \(12300 \times 4 = 49200\)

\(\implies 123 \times 456 = 738 + 6150 + 49200 = 56088.\)

Note that this is essentially the standard algorithm for multiplying numbers.

  123
× 456
—————
  738
 6150
49200
—————
56088

Fast exponentiation

We have seen that we multiply numbers via repeated doubling. In a similar way, we can raise a number to a power via repeated squaring. Here is a Python implementation:

def power(m, n):
    p = 1
    while n > 0:
       if n % 2: # n is odd
            p = p * m
        m = m * m
        n = n // 2
    return p

The loop invariant \(Q = m^n p\) can be used to prove that the function correctly returns the value of \(m^n\).

One thought on “Russian peasant multiplication and loop invariants”

Leave a Reply

Your email address will not be published. Required fields are marked *