Friday, January 4, 2008

History of the Computer - How Computers Multiply

By Tony Stockill

In previous articles, 'History of the Computer - How Computers Add' and '- Flip-flops - a basic counter' we looked at adders, and counters. Now we will consider how these building blocks can be used to perform multiplication.
In the Decimal system, we can multiply by 10 by adding a 0 to the end of a number. For example 4 with a zero added becomes 40, similarly 346 becomes 3460.We can expand this by adding 2 or 3 zeros to multiply by 100 or 1000.

THE SHIFT REGISTER

In the Binary system used in computers, we can multiply by 2 by adding a zero at the end of the number. Thus 110 (2+4=6 decimal) becomes 1100 (4+8=12 decimal). Similarly we can add more zeros and multiply by 4,8,16 etc. (decimal). This is one form of multiplication, the process is called shifting as each bit, 1 or 0 is shifted to the next bit position, and a zero is added in at the first bit position.

THE ALU

Several different techniques have been used to multiply using logic elements, as before these are usually described in a logic diagram as a 'black box' labeled multiplier. In an even more sophisticated logic diagram, this would be combined with other 'black boxes' such as adders, dividers, square roots, etc. to make one big 'black box' the ALU (arithmetic logical unit). The actual 'works' inside this unit are irrelevant to the overall design of the computer. All the designer needs to know is that if he puts two numbers into the ALU, and tells it to multiply them, he will get an output of the result.

Initially these boxes would have been made up physically of vacuum tubes, in a box the size of your bedroom, these have been gradually improved, replaced, miniaturised, until nowadays that will all fit on a chip. However the basic principles are the same.

MULTIPLICATION

If we analyse the concept of multiplication, we see that it is one of repetition (and we know computers excel at this). Take for example 2X4. This means take 4 lots of 2, and add them together, or 2+2+2+2=8. So to make a multiplier for a computer we can use an adder, which we have, and some method of counting, which we also have, as discussed in the earlier articles we mentioned.

MULTIPLIER LOGIC

For the example we just looked at, 2X4, our multiplier would have one input from the 2 (10 binary) going to a 4-bit adder. The output, or result, from the adder would be looped around to form the second input to the adder.

The second of the numbers to be multiplied, 4 (100 binary) sets a flip-flop counter to count down from 4 to 1, with one count pulse every time we add. Thus the counter is 'more than 1, which is the condition for the adder output to be routed to its input. The initial add would be 10 + 10 binary (2+2 decimal), giving 100 binary.

This result is returned to the input, gated by the counter 'more than 1' to be added to 10 again, giving 110 binary. We perform another add of 110 + 10 getting a result of 1000.
This time the counter has counted down to one, and blocks the adder input. At the same time it allows the adder result output to become the multiplier result.

APPLICATION

You can see how this simple example could be used in a scaled-up version capable of multiplying multi-bit numbers. All we need is a lot more adders, and a few logic gates to control them, maybe throw in a bit of timing, so that it doesn't all get mixed up! As we've said before, when you're talking in nanoseconds, you can get through a lot of calculations very quickly.
Still to come we will look at how negative numbers are represented in computers, and how they handle very large numbers with something called Floating Point Arithmetic.

Tony is an experienced computer engineer. He is currently webmaster and contributor to http://www.what-why-wisdom.com. A set of diagrams accompanying these articles may be seen at http://www.what-why-wisdom.com/history-of-the-computer-0.html.