How Does This Multiplication Method Work?

Date: 11/12/2003 at 19:15:18
From: Cathy
Subject: New Math Multiplication

I've just learned a new way to multiply, where all you have to do is 
double, split in half, and add.  You double down one column and take 
halves down the other, dropping remainders, until the halving column 
reaches 1.  Then you cross out the rows where the halving produced an 
even number and add the remaining numbers in the doubling column.

For example, to multiply 27 * 38, it would work like this:

27     38       cross out the rows with 38,4,2 since they're even and
54     19       add the numbers left in the doubling column.
108     9       54 + 108 + 864 = 1026 and 27 * 38 = 1026
216     4
432     2
864     1

Why does this work?  How could you extend this to division, where 
all you have to do is double, halve, and add?

Date: 11/12/2003 at 19:53:09
From: Doctor Tom
Subject: Re: New Math Multiplication

Hi Cathy,

That's nice!  I had not seen this method before.

What it amounts to is a standard multiplication, but using base 2.  
Let me illustrate by showing how a base-2 multiplication of those same 
two numbers would work:

   27 = 11011 (in base 2, 16 + 8 + 2 + 1)
   38 = 100110 (32 + 4 + 2)

Now if I do base-2 multiplication just like I'd do it in base-10, 
here's what it would look like when you multiply just before you add:

       11011
      100110
      ------
       00000
      11011
     11011
    00000
   00000
  11011
-------------

Now if you look at the terms that you need to add up to make the final 
total, each successive row is shifted by 1 place, which is equivalent 
to a multiplication by 2.  Thus the non-zero rows represent, from top 
to bottom:

   27 x 2
   27 x 4
   27 x 32

And this makes sense--if you add them together, you obtain 27(2 + 4 +
32) = 27 x 38.  Notice that in the left row of the sums in your
example, we've got 27, 27x2, 27x4, 27x8, and so on, but we've somehow
managed to toss out all the ones that shouldn't be there, leaving only
27x2, 27x4 and 27x32.

OK, so when do we get non-zero rows?  The answer is: whenever there's
a "1" in the binary expansion of 38.

Let's look at 38 and see how to figure out its binary expansion.  The 
first thing you want to find is if the final digit is 1.  That will 
occur if its final digit is odd.  To find the next most significant
binary bit, divide by 2, tossing the remainder if necessary, and look 
at the final digit of that.  If it's odd, there will be a 1 in the 
binary expansion, and so on.

When you did successive divisions by 2 to 38 in your example, you got:

38, 19, 9, 4, 2, 1

Look at the odd-even pattern here, where I write 0 for even and 1 for odd:

0,  1,  1,  0,  0,  1

This is just the binary expansion of 38, but in reverse order.

I hope that's enough to make it clear to you why the system works.  If 
not, go though a couple of other examples.  Notice that there's 
nothing special about the 27 side; whatever number you put in that 
column just keeps doubling up and you just need to select the right 
ones to make the binary multiplication work.  What you need to do is 
convince yourself that the other side where you successively divide 
indicates the proper positions for 1 bits in the number that you place 
in the position occupied by 38 in your example.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/13/2003 at 08:59:24
From: Doctor Peterson
Subject: Re: New Math Multiplication

Hi, Cathy.

This isn't really "new" at all; in fact, it traces its roots to 
ancient Egypt. (The Egyptians also did division more or less this 
way.) You can read about it here:

  Russian Peasant Multiplication.
    http://mathforum.org/dr.math/faq/faq.peasant.html 

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/