7.2.1 Multiplication by a Power of Two

If the multiplier is a power of two, then multiplication can be accomplished with a shift to the left. Consider the 4-bit binary number x = x₃ × 2³ + x₂ × 2² + x₁ × 2¹ + x₀ × 2⁰, where x_n denotes bit n of x. If x is shifted left by one bit, introducing a zero into the least significant bit, then it becomes $x_3\times 2^4+x_2\times 2^3+x_1\times 2^2+x_0\times 2^1+0\times 2^0=2\left(x_3\times 2^3+x_2\times 2^2+x_1\times 2^1+x_0\times 2^0+0\times 2^{-1}\right)$ Therefore, a shift of one bit to the left is equivalent to multiplication by two. This argument can be extended to prove that a shift left by n bits is equivalent to multiplication by 2ⁿ.

7.2.2 Multiplication of Two Variables

Most techniques for binary multiplication involve computing a set of partial products and then summing the partial products together. This process is similar to the method taught to primary schoolchildren for conducting long multiplication on base ten integers, but has been modified here for application to binary. The method typically taught in school for multiplying decimal numbers is based on calculating partial products, shifting them to the left and then adding them together. The most difficult part is to obtain the partial products, as that involves multiplying a long number by one base ten digit. The following example shows how the partial products are formed when multiplying 123 by 456.

The first partial product can be written as 123 × 6 × 10⁰ = 738. The second is 123 × 5 × 10¹ = 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:

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 7.4 shows the results of multiplying 101₁₀ by 89₁₀ 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.

Example 7.4

Equivalent Multiplication in Decimal and Binary

Binary multiplication can be implemented as a sequence of shift and add instructions. Given two registers, x and y, and an accumulator register a, the product of x and y can be computed using Algorithm 1. When applying the algorithm, it is important to remember that, in the general case, the result of multiplying an n bit number by an m bit number is (at most) an n + m bit number. For instance 11₂ × 11₂ = 1001₂. Therefore, when applying Algorithm 1, it is necessary to know the number of bits in x and y. Since x is shifted left on each iteration of the loop, the registers used to store x and a must both be at least as large as the number of bits in x plus the number of bits in y.

Assume we wish to multiply two numbers, x = 01101001 and y = 01011010. Applying Algorithm 1 results in the following sequence:

To multiply two n bit numbers, you must be able to add two 2n-bit numbers. On the ARM processor, n is usually assumed to be 32-bits, because that is the natural word size for the ARM processor. Adding 64-bit numbers requires two add instructions and the carry from the least-significant 32 bits must be added to the sum of the most-significant 32 bits. The ARM processor provides a convenient way to perform the add with carry. Assume we have two 64 bit numbers, x and y. We have x in r0, r1 and y in r2, r3, where the high order words of each number are in the higher-numbered registers, and we want to calculate x = x + y. Listing 7.1 shows a two instruction sequence for the ARM processor. The first instruction adds the two least-significant words together and sets (or clears) the carry bit and other flags in the CPSR. The second instruction adds the two most significant words along with the carry bit.

On the ARM processor, the algorithm to multiply two 32-bit unsigned integers is very efficient. Listing 7.2 shows one possible algorithm for multiplying two 32-bit numbers to obtain a 64-bit result. The code is a straightforward implementation of the algorithm, and some modifications can be made to improve efficiency. For example, if we only want a 32-bit result, we do not need to perform 64-bit addition. This significantly simplifies the code, as shown in Listing 7.3.

7.2.3 Multiplication of a Variable by a Constant

If x or y is a constant, then a loop is not necessary. The multiplication can be directly translated into a sequence of shift and add operations. This will result in much more efficient code than the general algorithm. If we inspect the constant multiplier, we can usually find a pattern to exploit that will save a few instructions. For example, suppose we want to multiply a variable x by 10₁₀. The multiplier 10₁₀ = 1010₂, so we only need to add x shifted left 1 bit to x shifted left 3 bits as shown below:

Now suppose we want to multiply a number x by 11₁₀. The multiplier 11₁₀ = 1011₂, so we will add x to x shifted left one bit plus x shifted left 3 bits as in the following:

If we wish to multiply a number x by 1000₁₀, we note that 1000₁₀ = 1111101000₂ It looks like we need one shift plus five add/shift operations, or six add/shift operations. With a little thought, the number of operations can be reduced from six to five as shown below:

Applying the basic multiplication algorithm to multiply a number x by 255₁₀ would result in seven add/shift operations, but we can do it with only three operations and use only one register, as shown below:

Most modern systems have assembly language instructions for multiplication, but hardware multiply units require a relatively large number of transistors. For that reason, processors intended for small embedded applications often do not have a multiply instruction. Even when a hardware multiplier is available, on some processors it is often more efficient to use shift, add, and subtract operations when multiplying by a constant. The hardware multiplier units that are available on most ARM processors are very powerful. They can typically perform multiplication with a 32-bit result in as little as one clock cycle. The long multiply instructions take between three and five clock cycles, depending on the size of the operands. Using the multiply instruction on an ARM processor to multiply by a constant usually requires loading the constant into a register before performing the multiply. Therefore, if the multiplication can be performed using three or fewer shift, add, and subtract instructions, then it will be equal to or better than using the multiply instruction.

7.2.4 Signed Multiplication

Consider the two multiplication problems shown in Figs. 7.1 and 7.2. Note that the result of a multiply depends on whether the numbers are interpreted as unsigned numbers or signed numbers. For this reason, most computer CPUs have two different multiply operations for signed and unsigned numbers.

If the CPU provides only an unsigned multiply, then a signed multiply can be accomplished by using the unsigned multiply operation along with a conditional complement. The following procedure can be used to implement signed multiplication.

1. if the multiplier is negative, take the two’s complement,

2. if the multiplicand is negative, take the two’s complement,

3. perform unsigned multiply, and

4. if the multiplier or multiplicand was negative (but not both), then take two’s complement of result.

Example 7.5 demonstrates this method using one negative number.

Example 7.5

Signed Multiplication Using Unsigned Math

7.2.5 Multiplying Large Numbers

Consider the method used for multiplying two digit numbers is base ten, using only the one-digit multiplication tables. Fig. 7.3 shows how a two digit number a = a₁ × 10¹ + a₀ × 10⁰ is multiplied by another two digit number b = b₁ × 10¹ + b₀ × 10⁰ to produce a four digit result using basic multiplication operations which only take one digit from a and one digit from b at each step.

This technique can be used for numbers in any base and for any number of digits. Recall that one hexadecimal digit is equivalent to exactly four binary digits. If a and b are both 8-bit numbers, then they are also 2-digit hexadecimal numbers. In other words 8-bit numbers can be divided into groups of four bits, each representing one digit in base sixteen. Given a multiply operation that is capable of producing an 8-bit result from two 4-bit inputs, the technique shown above can then be used to multiply two 8-bit numbers using only 4-bit multiplication operations.

Carrying this one step further, suppose we are given two 16-bit numbers, but our computer only supports multiplying eight bits at a time and producing a 16-bit result. We can consider each 16-bit number to be a two digit number in base 256, and use the above technique to perform four eight bit multiplies with 16-bit results, then shift and add the 16-bit results to obtain the final 32-bit result. This approach can be extended to implement efficient multiplication of arbitrarily large numbers, using a fixed-sized multiplication operation.

7.3.1 Division by a Power of Two

If the divisor is a power of two, then division can be accomplished with a shift to the right. Using the same approach as was used in Section 7.2.1, it can be shown that a shift right by n bits is equivalent to division by 2ⁿ. However, care must be taken to ensure that an arithmetic shift is used if the numerator is a signed two’s complement number, and a logical shift is used if the numerator is unsigned.

7.3.2 Division by a Variable

The algorithm for dividing binary numbers is somewhat more complicated than the algorithm for multiplication. The algorithm consists of two main phases:

1. shift the divisor left until it is greater than dividend and count the number of shifts, then

2. repeatedly shift the divisor back to the right and subtract whenever possible.

Fig. 7.5 shows the algorithm in more detail. Because of the complexity of the algorithm, division in hardware requires a significant number of transistors. The ARM architecture did not introduce a divide instruction until ARMv7, and even then it was not implemented on all processors. Many ARM systems (including the Raspberry Pi) do not have hardware division. However, the ARM processor instruction set makes it possible to write very efficient code for division.

Before we introduce the ARM code, we will take some time to step through the algorithm using an example. Let us begin by dividing 94 by 7. The result is shown below:

To implement the algorithm, we need three registers, one for the dividend, one for the divisor, and one for a counter. The dividend and divisor are loaded into their registers and the counter is initialized to zero as shown below:

Next, the divisor is shifted left and the counter incremented repeatedly until the divisor is greater than the dividend. This is shown in the following sequence:

Next, we allocate a register for the quotient and initialize it to zero. Then, according to the algorithm, we repeatedly subtract if possible, shift to the right, and decrement the counter. This sequence continues until the counter becomes negative. For our example this results in the following sequence:

When the algorithm terminates, the quotient register contains the result of the division, and the modulus (remainder) is in the dividend register. Thus, one algorithm is used to compute both the quotient and the modulus at the same time. There are variations on this algorithm. For example, one variation is to shift a single bit left in a register, rather than incrementing a count. This variation has the same two phases as the previous algorithm, but counts in powers of two rather than by ones. The following sequence shows what occurs after each iteration of the first loop in the algorithm.

The divisor is greater than the dividend, so the algorithm proceeds to the second phase. In this phase, if the divisor is less than or equal to the dividend, then the power register is added to the quotient and the divisor is subtracted from the dividend. Then, the power and Divisor registers are shifted to the right. The process is repeated until the power register is zero. The following sequence shows what the registers will contain at the end of each iteration of the second loop.

As with the previous version, when the algorithm terminates, the quotient register contains the result of the division, and the modulus (remainder) is in the dividend register. Listing 7.4 shows the ARM assembly code to implement this version of the division algorithm for 32-bit numbers, and the counting method for 64-bit numbers.

7.3.3 Division by a Constant

In general, division is slow. Newer ARM processors provide a hardware divide instruction which requires between two and twelve clock cycles to produce a result, depending on the size of the operands. Older processors must perform division using software, as previously described. In either case, division is by far the slowest of the basic mathematical operations. However, division by a constant c can be converted to a multiply by the reciprocal of c. It is obviously much more efficient to use a multiply instead of a divide wherever possible. Efficient division of a variable by a constant is achieved by applying the following equality:

$\begin{array}{l}\hfill x÷c=x\times \frac{1}{c}.\end{array}$

The only difficulty is that we have to do it in binary, using only integers. If we modify the right-hand side by multiplying and dividing by some power of two (2ⁿ), we can rewrite Eq. (7.1) as follows:

$\begin{array}{l}\hfill x÷c=x\times \frac{2^n}{c}\times 2^{-n}.\end{array}$

Recall that, in binary, multiplying by 2ⁿ is the same as shifting left by n bits, while multiplying by 2⁻ⁿ is done by shifting right by n bits. Therefore, Eq. (7.2) is just Eq. (7.1) with two shift operations added. The two shift operations cancel each other out. Now, let

$\begin{array}{l}\hfill m=\frac{2^n}{c}.\end{array}$

We can rewrite Eq. (7.2) as:

$\begin{array}{l}\hfill x÷c=x\times m\times 2^{-n}.\end{array}$

We now have a method for dividing by a constant c which involves multiplying by a different constant, m, and shifting the result. In order to achieve the best precision, we want to choose n such that m is as large as possible with the number of bits we have available.

Suppose we want efficient code to calculate x ÷ 23 using 8-bit signed integer multiplication. Our first task is to find $m=\frac{2^n}{c}$ such that 01111111₂ ≥ m ≥ 01000000₂. In other words, we want to find the value of n where the most significant bit of m is zero, and the next most significant bit of m is one. If we choose n = 11, then

$m=\frac{2^{11}}{23}\approx 89.0434782609.$

Rounding to the nearest integer gives m = 89. In 8 bits, m is 01011001₂ or 59₁₆. We now have values for m and n, and therefore we can apply Eq. (7.4) to divide any number x by 23. The procedure is simple: calculate y = x × m, then shift y right by 11 bits.

However, there are two more considerations. First, when the divisor is positive, the result for some values of x may be incorrect due to rounding error. It is usually sufficient to increment the reciprocal value by one in order to avoid these errors. In the previous example, the number would be changed from 59₁₆ to 5A₁₆. When implementing this technique for finding the reciprocal, the programmer should always verify that the results are correct for all input values. The second consideration is when the dividend is negative. In that case it is necessary to subtract one from the final result.

For example, to calculate 101₁₀ ÷ 23₁₀ in binary, with eight bits of precision, we first perform the multiplication as follows:

Then shift the result right by 11 bits. 10001100011101₂ shifted right 11₁₀ bits is: 100₂ = 4₁₀. If the modulus is required, it can be calculated as 101 mod 23 = 101 − (4 × 23) = 9, which once again requires multiplication by a constant.

In the previous example the shift amount of 11 bits provided the best precision possible. But how was that number chosen? The shift amount, n, can be directly computed as

$\begin{array}{l}\hfill n=p+⌊{log}_{2}c⌋-1,\end{array}$

where p is the desired number of bits of precision. The value of m can then be computed as

$\begin{array}{l}\hfill m=\left\{\begin{array}{cc}\frac{2^n}{c}+1& c>0,\\ \frac{2^n}{c}& \text{otherwise}.\end{array}\right.\end{array}$

For example, to divide by the constant 33, with 16 bits of precision, we compute n as

$n=16+⌊{log}_{2}33⌋-1=16+⌊5.044394⌋-1=16+5-1=20,$

and then we compute m as

$m=\frac{2^{20}}{33}+1=31776.030303\approx 31776={\text{7C20}}_{16}.$

Therefore, multiplying a 16 bit number by 7C20₁₆ and then shifting right 20 bits is equivalent to dividing by 33.

Example 7.6 shows how to calculate m and n for division by 193. On the ARM processor, division by a constant can be performed very efficiently. Listing 7.5 shows how division by 193 can be implemented using only a few lines of code. In the listing, the numbers are 32 bits in length, so the constant m is much larger than in the example that was multiplied by hand, but otherwise the method is the same.

On processors without the multiply instruction, we can use the technique of shifting and adding shown previously. If we wish to divide by 23 using 32 bits of precision, we compute the multiplier as

$m=\frac{2^{32+4-1}}{23}+1=\frac{2^{35}}{23}+1=1493901669.17\approx 1493901669={\text{590B2165}}_{16}.$

That is 01011001000010110010000101100101₂. Note that there are only 12 non-zero bits, and the pattern 1011001 appears three times in the 32-bit multiplier. The multiply can be implemented as 2²⁴(2⁶x + 2⁴x + 2³x + 2⁰x) + 2¹³(2⁶x + 2⁴x + 2³x + 2⁰x) +2²(2⁶x + 2⁴x + 2³x + 2⁰x) + 2⁰x. So the following code sequence can be used on processors that do not have the multiply instruction:

7.3.4 Dividing Large Numbers

Section 7.2.5 showed how large numbers can be multiplied by breaking them into smaller numbers and using a series of multiplication operations. There is no similar method for synthesizing a large division operation with an arbitrary number of digits in the dividend and divisor. However, there is a method for dividing a large dividend by a divisor given that the division operation can operate on numbers with at least the same number of digits as in the divisor.

Suppose we wish to perform division of an arbitrarily large dividend by a one digit divisor using a basic division operation that can divide a two digit dividend by a one digit divisor. The operation can be performed in multiple steps as follows:

1. Divide the most significant digit of the dividend by the divisor. The result is the most significant digit of the quotient.

2. Prepend the remainder from the previous division step to the next digit of the dividend, forming a two-digit number, and divide that by the divisor. This produces the next digit of the result.

3. Repeat from step 2 until all digits of the dividend have been processed.

4. Take the final remainder as the modulus.

The following example shows how to divide 6189 by 7 using only 2-digits at a time:

This method can be applied in any base and with any number of digits. The only restriction is that the basic division operation must be capable of dividing a 2n digit number by an n digit number and producing a 2n digit quotient and an n digit remainder. for example, the div instruction available on Cortex M3 and newer processors is capable of dividing a 32-bit dividend by a 32-bit divisor, producing a 32-bit quotient. The remainder can be calculated by multiplying the quotient by the divisor and subtracting the product from the dividend. Using this division operation it is possible to divide an arbitrarily large number by a 16-bit divisor.

We have seen that, given a divide operation capable of dividing an n digit number by an n digit number, it is possible to divide a dividend with any number of digits by a divisor with $\frac{n}{2}$ digits. Unfortunately, there is no similar method to deal with an arbitrarily large divisor, or to divide an arbitrarily large dividend by a divisor with more than $\frac{n}{2}$ digits. In those cases the division must be performed using a general division algorithm as shown previously.