Page 202 - ARM 64 Bit Assembly Language

190 Chapter 7

123
× 456
7 3 8 (this is 123 x 6)
6150 (this is 123 x 5, shifted one position to the left)
+ 49200 (this is 123 x 4, shifted two positions to the left)
56088

0 1
The first partial product can be written as 123 × 6 × 10 = 738. The second is 123 × 5 × 10 =
2
6150, and the third is 123 × 4 × 10 = 49200. In practice, we usually leave out the trailing
zeros. The procedure is the same in binary, but is simpler because the partial product involves
multiplying a long number by a single base 2 digit. Since the multiplier is always either zero
or one, the partial product is very easy to compute. The product of multiplying any binary
number x by a single binary digit is always either 0 or x. Therefore, the multiplication of two
binary numbers comes down to shifting the multiplicand left appropriately for each non-zero
bit in the multiplier, and then adding the shifted numbers together.

Suppose we wish to multiply two four-bit numbers, 1011 and 1010:

1 0 1 1 this is 11 10
× 1 0 1 0 this is 10 10
0 0 0 0 1011 x 0
1 0 1 1 1011 x 1, shifted one position to the left
0 0 0 0 1011 x 0, shifted two positions to the left
+ 1011 1011 x 1, shifted three positions to the left
1101110 this is 110 10

Notice in the previous example that each partial sum is either zero or x shifted by some
amount. A slightly quicker way to perform the multiplication is to leave out any partial sum
which is zero. Example 14 shows the results of multiplying 101 10 by 89 10 in decimal and
binary using this shorter method. For implementation in hardware and software, it is easier
to accumulate the partial products, by adding each to a running sum, rather than building a
circuit to add multiple binary numbers at once. This results in an algorithm with O(n) com-
plexity, where n is the number of bits in the multiplier. There are multiplication algorithms
that give even better performance, an some processors use combinatorial multiplication cir-
cuits, which are very fast, but require a large number of transistors and consume a great deal
of power.