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

From stackoverflow

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 20 09:08:06 2017

@author:
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:
1. Write the two numbers down next to each other.
2. Divide the first in half, rounding down to an integer,
and write the result below it.
3. Double the second number, writing the result below it.
4. Continue this halving / doubling until we are left
with 1 in the first column.
5. 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.

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 (p2, 2q)
    (when p is even) or by (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⋅q=p/2 2p⋅.

    In the second case, when p is odd, p−1/2⋅2q=p⋅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.

The ancient Egyptains had a similar precursor method:
    en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
    – Henno Brandsma Mar 17 at 4:55

Note this method can be adapted for other number bases,
there is nothing special about 2, except for the fact that it is
immediate to calculate mod 2 of a base 10 representation.
To adapt it for base b, divide by b in each step and record the
remainder, later multiply each reminder by the right column and add.
Also, stop the first column when reaching a number less than b.
The right column is generated by multiplying by b.

And this is an example, 73⋅217:
(73,217)(36,434)(18,868)(9,1736)(4,3472)(2,6944)(1,13888)
Then 73⋅217=217+1736+13888=15841, which is correct.
"""

def russian_peasant_multiplication(p, q, acc=0):
    '''
    Returns de product of a and b if acc == 0
    using recursive conversion of the first factor to binary
    '''
    print(p, q, acc + q)
    if p == 1:
        return acc + q
    elif (p % 2) == 0:
        return russian_peasant_multiplication(p // 2, q * 2, acc)
    else:
        return russian_peasant_multiplication(p // 2, q * 2, acc + q)

assert russian_peasant_multiplication(73, 217) == 15841

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s