Binary Multiplication

http://www.exploringbinary.com/binary-multiplication/


This is the third of a four part series on “pencil and paper” binary arithmetic, which I’m writing as a supplement to my binary calculator. The first article discusses binary addition; the second article discusses binary subtraction; this article discusses binary multiplication.

An Example of Binary Multiplication

Example of Binary Multiplication

The pencil-and-paper method of binary multiplication is just like the pencil-and-paper method of decimal multiplication; the same algorithm applies, except binary numerals are manipulated instead. The way it works out though, binary multiplication is much simpler. The multiplier contains only 0s and 1s, so each multiplication step produces either zeros or a copy of the multiplicand. So binary multiplication is not multiplication at all — it’s just repeated binary addition!

Decimal Multiplication

To multiply two multiple-digit decimal numbers, you first need to know how to multiply two single-digit decimal numbers. This requires the memorization of 100 facts, or 55 facts if you exclude the commutative or “turnaround” facts. These facts are usually represented in a “multiplication table,” also known as a “times table.” Example facts are 2 x 9 = 18, 9 x 7 = 63, and 1 x 6 = 6.

A multiplication problem is written with one number on top, called the multiplicand, and one number on the bottom, called the multiplier. The algorithm has two phases: the multiplication phase, where you produce what are called partial products, and the addition phase, where you add the partial products to get the result.

In the multiplication phase, the digits of the multiplier are stepped through one at a time, from right to left. Each digit of the multiplicand is then multiplied, in turn, by the current multiplier digit; taken together, these single-digit multiplications form a partial product. The answer to each single-digit multiplication comes from the multiplication table. Some of these answers are double-digit numbers, in which case the least significant digit is recorded and the most significant digit is carried over to be added to the result of the next single-digit multiplication.

For example, let’s multiply 3.87 and 5.3:

An Example of Decimal Multiplication

Example of Decimal Multiplication

There are two digits in the multiplier, so there are two partial products: 1161 and 19350. Each partial product has its own set of carries, which are crossed out before computation of the next partial product. Here is the multiplication phase, broken down into steps:

Steps of Decimal Multiplication (Multiplication Phase Only)

Steps of Decimal Multiplication (Multiplication Phase Only)

When the multiplication phase is done, the partial products are added, and the decimal point is placed appropriately. (If there were any minus signs, they would be taken into account at this point as well.) This gives the answer 20.511.

Binary Multiplication

Binary multiplication uses the same algorithm, but uses just three order-independent facts: 0 x 0 = 0, 1 x 0 = 0, and 1 x 1 = 1 (these work the same as in decimal). If you perform the multiplication phase with these facts, you’ll notice two things: there are never any carries, and the partial products will either be zeros or a shifted copy of the multiplicand.

Observing this, you’ll realize there’s no need for digit-by-digit multiplication, which means there’s no need to consult a times table — which means there’s no multiplication, period! Instead, you just write down 0 when the current digit of the multiplier is 0, and you write down the multiplicand when the current digit of the multiplier is 1.

In the introduction, I showed this example: 1011.01 x 110.1. I wrote it as if you followed the decimal algorithm to the letter. Here’s how it looks if you follow the simpler “write zero or multiplicand” algorithm (it’s the same result, but with blanks representing 0s; this matches better conceptually with what we are now doing):

An Example of Binary Multiplication (Simplified View)

Example of Binary Multiplication (Simplified View)

Here’s what the “multiplication” phase looks like, step-by-step:

Steps of Binary Multiplication (Multiplication Phase Only)

Steps of Binary Multiplication (Multiplication Phase Only)

Each step is the placement of an entire partial product, unlike in decimal, where each step is a single-digit multiplication (and possible addition of a carry).

In the addition phase, the partial products are added using binary addition, and then the radix point is placed appropriately. This gives the answer 1001001.001.

Checking the Answer

You can check the answer by converting the operands to decimal, doing decimal multiplication, and then converting the decimal answer to binary. 1011.01 = 11.25, and 110.1 = 6.5. Their product is 73.125, which is 1001001.001, the answer we got using binary multiplication.

You can also check the answer using my binary calculator.

Discussion

Computers don’t multiply in exactly this way, but they do exploit the simplified view of binary multiplication that I’ve described.

Dingbat

8 Responses to “Binary Multiplication”

  1. Shaun Says:

    Hi Rick,

    Would you mind if I include this post in the Math and Multimedia Carnival #21, being hosted on my site, Math Concepts Explained at http://sk19math.blogspot.com. This is a great introduction to and demonstration of working with binary arithmetic!

    Cheers,
    Shaun

  2. Rick Regan Says:

    Shaun,

    Sure, go ahead. I’m glad you found it useful.

    Rick

  3. Wilf Says:

    Hi,

    At the addition stage what happens when you add 1+1+1+1 for example?
    v
    10111100
    10011101
    10110010
    10110010

  4. Rick Regan Says:

    @Wilf,

    Think of it as three different addition problems: 1+1 = 10, 10 + 1 = 11, and 11 + 1 = 100. You might be able to do that last one in your head, but if not, just write it out:

     11
      11
     + 1
     ---
     100
    
  5. Oz Says:

    OK so .1 in binary is .5 in decimal, .01 is .25 and .001 is .125. Where do I learn how to display 3.87 and 5.3 in binary? Thank you.

  6. Rick Regan Says:

    @Oz,

    I’m assuming you want the method that converts by hand. Separate the integer and fractional parts and convert them separately. For the integer part, use “repeated division by 2″; for the fractional part, use “repeated multiplication by 2″ (search the Web for the details).

    For example, convert 14.1 to binary. Start with the integer part:

    14/2 = 7 remainder 0
    7/2 = 3 remainder 1
    3/2 = 1 remainder 1
    1/2 = 0 remainder 1

    The answer for the integer part is the remainders reversed: 1110.

    Now do the fractional part:

    0.1 * 2 = 0.2
    0.2 * 2 = 0.4
    0.4 * 2 = 0.8
    0.8 * 2 = 1.6
    0.6 * 2 = 1.2
    0.2 * 2 = … (repeats)

    The answer for the integer part is 0.00011001100110011…

  7. Oz Says:

    Thank you for your swift response! I had assumed operations in binary would be easy – and they are until one hits division. I can’t even handle 5/3. Thanks again.

  8. Asukele Says:

    It really helped me and I think I’ll be here more often as I go through college

Leave a Comment

(To reduce spam, cookies must be enabled)


css.php