Welcome to the next post in my series on binary numbers and binary arithmetic. In todays post we’re again going to build on what we have learnt in my previous posts on binary addition and binary subtraction and see how we can perform multiplication in binary.
Before we dive in, I first wanted to take a moment to establish some terminology. It’s going to make it a lot easier to explain things as we go forward if we both have a common language.
An example of how we write a multiplication problem is shown below.
On the top we have the multiplicand. This is the number we want to multiply. On the bottom we have the multiplier. This is the number we will use to multiply the multiplicand. As we move through the examples later in this post, I’ll use these terms to explain the steps you need to take to perform the multiplication.
The Four Phases of Multiplication
There are a number of phases to the multiplication process:
The Alignment Phase: In the alignment phase the first thing we do is to align the numbers we wish to multiply so that their right-hand digits align. In cases where the numbers have a different number of digits after the radix point (remember the radix point separates the whole parts of the number from the fractional part), this means that the radix points of the two numbers will not align. Don’t worry about that. We will solve that in a later phase.
The Multiplication Phase: In this phase we produce a set of partial products by combining a number of single digit multiplications. Starting at the right-hand side, we take each digit of the multiplier and in turn use that digit to multiply each of the digits in the multiplicand. The results of these individual multiplications are then combined to create a partial product. Where the results of an individual multiplication has multiple digits the least significant digit is written down and the most significant digit is carried over to be added to the result of the next single digit multiplication. Once all the digits have been multiplied and the partial product has been calculated, the next digit in the multiplier is taken and the steps above are repeated. Each time a subsequent partial product is calculated the partial product is shifted one column to the left when compared to the last partial product. All spare columns to the right are then filled with zeros. (This might become a little clearer when we look at our example.) Once this is done for all digits in the multiplier and all the digits have been multiplied by all the digits in the multiplicand we should have one partial product for each of the digits in our multiplier. At this point we move on to the next phase.
The Addition Phase: In the addition phase, we calculate our result by adding all the partial products we calculated in phase 1.
Placing the Radix Point and Adding the Sign: The final step in the process is to place the radix point and calculate the sign of the number. As we’ve learnt previously, the radix point separates the whole numbers from the fractional numbers and in decimal is also known as the decimal point. The key thing to remember when placing the radix point in our final result is that our result will have the same number of digits after the radix point as there are after the radix point in each of the numbers we’re trying to multiply combined. For example if we were multiplying 23.6 x 27.564 we would have 4 digits to the right of the radix point in our answer as there is 1 digit after the radix point in our first number and another 3 after the radix point in our second number.
Multiplication in Decimal
Now that we have the basic phases clear, let’s work through an example.
To get started, lets walk through an example in decimal. It may be a refresher for you but it helps to illustrate the steps taken to perform multiplication in a number base you will be used to before we introduce the complication of performing it in binary.
In order to successfully perform multiplication of any two decimal numbers the main thing you need to remember is your multiplication tables. All decimal multiplication is based a number of simple single digit multiplications that are then added together.
For our example, imagine we were trying to work out how much it was costing us to run our computer per week and we have worked out it is consuming 23.4 units of electricity per week and each unit cost us 6.7 cents (Yeah… I know… just imagine…)
Stage 1: Align the Two Numbers
As I indicated above, the first stage of the process is to align our two numbers and write out our multiplication problem. As 23.4 (our multiplicant) and 6.7 (our multiplier) both have a single digit to the right of the decimal place, this is a pretty easy task in this case.
Stage 2: Calculating the Partial Products
Stage 2 involves calculating the partial products. As we have two digits in our multiplier we will have two partial products.
Calculating the First Partial Product
Let’s start calculating our first partial product. To begin we take the right-most digit in the multiplier (the 7 of the 6.7) and multiply it by the first digit in the multiplicand (the 4 of the 23.4). 4 x 7 = 28. We put an 8 as the first digit in our partial product and then carry the 2.
Next we multiply the right-most digit in the multiplier (the 7 of the 6.7) by the second digit in the multiplicand (the 3 of the 23.4) and then add any numbers we carried. 3 x 7 = 21, add the 2 we carried from the previous step = 23. We put a 3 as the second digit in our partial product and then carry the 2.
We then multiply the right-most digit of the multiplier (the 7 of the 6.7) by the third digit in the multiplicand (the 2 of the 23.4) and again add any numbers we carried. 2 x 7 = 14, add the 2 we carried from the previous step = 16. We put 6 as the next digit of our partial product and as we have no more digits to multiply, we place the carried 1 into the next column. The result, our first partial product of 1638.
Calculating the Second Partial Product
Having multiplied the first digit of our multiplier, we now move on to the second digit. As this second digit is an order of magnitude larger than the first digit we multiplied, we put a zero as the first digit of our second partial product.
Having got ourselves set up, we now take the second digit in the multiplier (the 6 of the 6.7) and multiply it by the first digit in the multiplicand (the 4 of the 23.4). 4 x 6 = 24. We put the 4 as the second digit in the partial product and carry the 2.
Next, we multiply the second digit in the multiplier (the 6 of the 6.7) and multiply that by the second digit of the multiplicand (the 3 of the 23.4) before adding anything we carried from the previous step. 3 x 6 = 18, add the 2 we carried = 20. We put the 0 as the third digit in our partial product and again carry the 2.
Next, we multiply the second digit in the multiplier (the 6 of the 6.7) by the third of the digits in the multiplicand (the 2 of the 23.4) and again add anything we carried. 2 x 6 = 12, add the 2 we carried = 14. We put the 4 as the next digit in our partial product and as there are no more digits to multiply, put the 1 in the next column. The result is our second partial product of 14040.
Stage 3: Adding the Partial Products
The next phase is about adding the two partial products together. Starting in the rightmost column, we add the 8 of the first partial product with the 0 of the second partial product and get 8 which we place in the first column of our result.
Next we move on to the second column, adding the 3 of the first partial product to the 4 of the second partial product to get 7. This is added as the second digit of our result.
The third column sees us adding the 6 of the first partial product to the 0 of the second partial product to get 6 which is placed as the third digit in our result.
In the fourth column we add the 1 from the first partial product to the 4 of the second partial product to get 5 which we write as the fourth digit of the result.
Finally, we take the 1 of the second partial product and move that down as the fifth digit in our result. That gives us a result of 15678.
Stage 4: Locating the Radix Place
The next step is to place the radix or decimal place. The rule is that our result will have the same number of places as there are in all the numbers we were multiplying together. Our multiplicand 23.4 has only one place and our multiplier also has one place giving us a total of 2. Starting to the right of the rightmost digit in our result, we therefore move the decimal place 2 places to the left to get our final result of 156.78.
Binary Multiplication is generally simpler than decimal multiplication. Instead of needing to know your multiplication tables you only really need to know three things:
1 x 1 = 1
0 x 1 = 0
1 x 0 = 0
When you perform multiplication with binary you will notice that there are never any carries and the partial products will either be zero or a shifted version of the multiplicand. Let’s look at another example. Imagine we were trying to multiply the following: 1.01 x 10.10 (it’s stretching the analogy somewhat to imagine this is also your electricity bill!). Again we will follow the same stages as we did with decimal multiplication.
So there we have it. Binary Multiplication. Slightly simpler than decimal equivalent due to the reduced need to know all your different multiplication tables but still an essential building block of binary mathematics. Try it for yourself.
Image credit: http://flic.kr/p/b9KQCk