How we multiply: Part 2

What I’m gonna teach to my future kids… part 2.

Read on if you wish to mentally multiply numbers quickly, know some of the best human calculators, or maybe if you have time appreciating my work.

Now here’s a more interesting part: how to actually multiply two integers without using your classic abacus or your 3rd grade long division.

A few that I mentioned here are the well known Babbage algorithm, Karatsuba algorithm, and Lattice multiplication.

Btw, here’s a bonus to help you with your CompSci homework.  Multiplying two numbers without the ‘*’ operator:

def nostar(x, y):
    if x == 0 or y == 0:
        return 0
    elif y == 1:
        return x
    elif x == 1:
        return y
    
    return x + nostar(x, y - 1)

I think this looks elegant and simple, albeit the use of recursion.  In my computer this fails when y is greater than 978, though you can always create your own method to handle large recursion depth,… say by allocating extra space in the stack memory.

Two numbers x, y with n digits can be represented as follow:

This is similar to how you would say a number in English (e.g. 1400 is ‘one thousand and four hundred’).  Here represents base, and let m be a number less than n.  In our example earlier m=3.  When m=2 it would be similar to saying ‘fourteen-hundred’.

Define

where

This method requires four multiplications.  As ironic as it may seem, we have reduced the number of digits that we need to multiply, and the rest is addition.  This is something you can definitely do in your head.

I encourage you to try this algorithm!

In my implementation is base.

# Number representation
def rep(x, y, b):
    n = min(len(str(x)), len(str(y)))
    m = n - 1
    
    B = b
    
    x_1 = int(math.ceil(x/B**m))
    y_1 = int(math.ceil(y/B**m))
    
    x_0 = x % (x_1 * B**m)
    y_0 = y % (y_1 * B**m)
    
    return x_0, x_1, y_0, y_1, B, m
def babbage(x, y, b):
    x_0, x_1, y_0, y_1, B, m = rep(x, y, b)

    
    z_2 = x_1 * y_1
    z_1 = x_1 * y_0 + x_0 * y_1
    z_0 = x_0 * y_0
    
    xy = z_2 * B**(2*m) + z_1 * B**m + z_0
    
    return xy

Karatsuba noticed that we can do better by having only three multiplications.

Notice that z_1 is written differently, here.

def karatsuba(x, y, b):
    x_0, x_1, y_0, y_1, B, m = rep(x, y, b)
    
    z_0 = x_0 * y_0
    z_2 = x_1 * y_1
    z_1 = (x_1 + x_0)*(y_1 + y_0) - z_0 - z_2
    
    xy = z_2 * B**(2*m) + z_1 * B**m + z_0
    
    return xy

A more efficient implementation of Karatsuba algorithm can be written down as follows:

def karatsuba2(x,y, b):
    x_0, x_1, y_0, y_1, B, m = rep(x, y, b)
    
    b = B**m
          
    xy = (b**2 + b)*x_1*y_1 - b*(x_1 - x_0)*(y_1-y_0) + (b+1)*x_0*y_0
    
    return xy

Lattice Multiplication

I think Lattice Multiplication is certainly a unique way to multiply two different numbers.  In my view, it takes advantage that digit-wise multiplication only result in at most an extra digit.  It is equivalent to long multiplication, only that it is represented in lattice, as the name says.

A great explanation of Lattice Multiplication can be found here: Lattice Multiplication Method

Its implementation is given here:

def lattice(x, y):
    x = [int(i) for i in str(x)]
    y = [int(i) for i in str(y)]
    
    length = len(str(x)) + len(str(y))
    
    diagonals = [0] * length 
    for index_x, digit_x in list(enumerate(x)):
        for index_y, digit_y in list(enumerate(y)):
            value = int(digit_x) * int(digit_y)
            diagonals[index_x+index_y+0] += value // 10
            diagonals[index_x+index_y+1] += value %  10
                     
    print diagonals

    digits = []
    rest   = 0
    for value in reversed(diagonals):
        value += rest
        if value > 9:
            rest = value / 10
            digits.insert(0, value % 10)
        else:
            rest = 0
            digits.insert(0, value)

    if rest > 0:
        digits.insert(0, rest)

    if digits[0] == 0:
        del digits[0]
        
    for i in xrange(len(digits) - 1, len(digits) - 2*length , -1):
        print digits
        del digits[i]
    return digits

Multiplication using Squares:

One of the lesser known algorithms is by A.C. Aitken, famous for Aitken extrapolation (or Aitken Delta Squared method) that speeds up rate of convergence of series, takes advantage of squares.

It will surely minimize calculation time given that you know your squares (see previous article).

Check this out:

Simple.  Elegant.  (Insert adjectives Steve Jobs would say here).  Revolutionary.

Its implementation:

def aitkenMult(x, y):
    xy = ((x+y)/2)**2 - ((x-y)/2)**2
         
    return xy

 

I have only shown you some of the multiplication algorithms that you can do in your head.  There are so many more that can make me go on and write about multiplication algorithms to part 13 (this number is no accident).

The point is to show you that such simple task; multiplication, takes many forms algebraically, and their forms are taken into account in fields such as Approximation Theory.

There are many Mathematicians who exhibited power and excellence in mental arithmetic.  Some of the well known ones are Gauss, Ampere, Aitken, John von Neumann, Ramanujan, and Jakow Trachtenberg, to name a few.

John von Neumann is said to have the ability to multiply and divide two 8-digit numbers in his head by the age of 6.

Jakow Trachtenberg,  the Russian-Jewsih engineer, developed Trachtenberg system while being held in Nazi concentration camp while feeling bored.

A.C. Aitken practiced memorization for numbers only when he was 15.  Unlike others mentioned above, he developed his skill instead of naturally acquiring them.

“Only at the age of 15 did I feel I might develop a real power and for some years about that time, without telling anyone, I practised mental calculation from memory like a Brahmin Yogi, a little extra here, a little extra there, until gradually what had been difficult at first became easier and easier…”

(P C Fenton, To catch the spirit: The memoir of A C Aitken (Otago, 1995).)

Ramanujan, famously known for Ramanujan Sum in Number Theory, is said to have Hindu Goddess Namagiri whispered equations and solutions to his ear.  Like me, Ramanujan hates doing proofs.  Here’s a great article about Ramanujan

More about mental arithmetic can be found here: Mental Arithmetic

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