How we multiply: Part 1

This is what I’m going to teach to my future kids.

Long time ago, in a nebula far, far away, I started wondering how we were taught to multiply numbers as kids.  I wondered if the ways we would multiply numbers are different based on region.

After a little research I found out that there is one (almost) universal way to multiply, and that is with long multiplication  This is the way I was taught, to say the very least.  It looks something like this:

LongMultiplication2

You multiply 384 by 6 to obtain 2304, then add that result by a left-shifted 384 * 5 (blank space is considered 0) to get 21504.  Simple enough.

This method is clearly Θ(n2).  Nothing special here.  Its implementation for integers can be found here (note that the implementation is designed so that it represents the way I [and maybe most people] think) :

def longMult(x, y):
    x_arr = [int(d) for d in str(x)]
    y_arr = [int(d) for d in str(y)]

    if len(x_arr) < len(y_arr):
        x_arr, y_arr = y_arr, x_arr
        
    res = [[0 for i in xrange(len(y_arr) + len(x_arr))] for j in xrange(len(y_arr))]
    
    for i in xrange(len(y_arr) - 1, -1, -1):
        m = len(y_arr) - 1 - i
        carry = 0
        for j in xrange(len(x_arr) - 1, -1, -1):
            res[m][i+j+1] = x_arr[j] * y_arr[i] + carry
            carry = res[m][i+j+1] / 10
            res[m][i+j] = carry
            res[m][i+j+1] = (res[m][i+j+1] % 10)

    for i in xrange(len(y_arr)):
        
        s = ''.join(map(str, res[i]))
        res[i] = int(s)
        
    return sum(res)

Two things:

  1. I break numbers to individual digits.  (For me this consistency is especially useful for a number bigger than three digits.
  2. I make use of a two-dimensional array.  Some people choose to add the numbers as they go, but I prefer to add them last.  (The abacus user will clearly add the numbers as they go)

The implementation can be changed to handle floating point numbers or numbers with different base.

If you’re ever curious on how computers multiply, it’s about the same.  It’s just that the numbers are in binary form, and it’s using AND operator so that two binary digits result in 0 if either bit is a 0. Check this:

       1001   (this is 9 in decimal)
     x 1110   (this is 14 in decimal)
     ______
       0000   (1001 x 0)
      1001    (1001 x 1, shifted one position to the left)
     1001     (1001 x 1, shifted two positions to the left)
  + 1001      (1001 x 1, shifted three positions to the left)
  _________
    1111110   (this is 126 in decimal)

Computers are just simply so efficient when we’re dealing with huge numbers  (Computer 1 – 0 Human).

And now here’s the point where I attempt to make a comeback against the computer: squaring numbers.

As kids we’d usually have to memorize squares of a number (e.g. 9×9 = 81) known as the multiplication table.  Having a table inside your head is fairly efficient, as we’d have no problem multiplying larger numbers such as 8000 × 8000 = 64000000.

It is quite handy to actually have a table for squares, and we’ll see why later.  I’ve found out that most of my peers have excellent memories on squaring a number up to 20 something.  If you ask me I memorize up to 40.  If you’re impressed with that my friend Alvin who is now, as of this writing is in high school, is able to memorize up to 100, and compute higher squares and multiply two 3 digit numbers in a matter of seconds.

Anyways, here’s how you can quickly square a number between 41 and 59 in your head:

def quickSquare(x):
    if x in range (1-41):
        return x**x
    
    elif x in xrange (41, 50):
        z = int(str(x)[1])
        w = (10 - z)**2
        if w < 10:
            w = '0' + str(w)
        
        return int(str(15 + z) + str(w))
        
    
    elif x in xrange (50, 60):
        z = int(str(x)[1])
        
        w = z**2
        if w < 10:
            w = '0' + str(w)
        return int(str(25 + z) + str(w))
  
        
    elif x in xrange(61, 100):
        return ((2*x % 100)*100) + (abs(100 - x)**2)
        
    elif x in xrange(100, 150):
        return (10000 + ((2*x % 100)*100) + (abs(100 - x)**2))

As mentioned before, I have squares between 1-40 memorized so I don’t bother with that.  To see what’s going on in the code, here’s an example:

Squaring anything between 41-49 (example here is 42; the meaning of life squared [get the joke?]):

  1. Take number 15 and add it to the second digit (here it’s 2 so 15 + 2 = 17)
  2. Subtract 10 from the second digit and square it (here it’s 2 so (10 – 2)² = 64)
  3. Put together those two numbers (here they are 17 and 64 so 1764)

Squaring anything between 50-59 (example here: 57):

  1. Take number 25 and add it to the second digit (25 + 7 = 32)
  2. Take the square of the second digit (7²49)
  3. Put together those two numbers (3249)

Squaring anything between 61 to 99 (example here is x = 69):

  1. 2x mod 100 * 100 = 3800
  2. |100 – x|² = 961
  3. Add numbers from step 1 and 2 = 4761

You can see now why I find it useful to memorize squares between 1-40.  Also, for every interval of 49 numbers, you can simply use the last method and add an extra 10000.  For example, 131²:

  1. 2x mod 100 * 100 = 6200
  2. |100 – x|² = 961
  3. Add numbers from step 1 and 2 = 7161
  4. Add 10000 so 17161

The tricky part is that higher numbers will require you to think recursively.  The downside of this method is in step 2.  If the number obtained in step 2 is larger than 60, you’ll have to recompute the square of that number using the same method.

This is why I’ll stop my implementation here.  It is designed to share how I think anyway, not to speed up computer multiplication.  (Computer 1 – 1 Human)

Next part I’ll post about other ways to multiply two distinct integers: Babbage, Karatsuba, Lattice multiplication included.

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