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 four bit binary number $x=x_3\times 2^3+x_2\times 2^2+x_1\times 2^1+x_0\times 2^0$, 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(x_3\times 2^3+x_2\times 2^2+x_1\times 2^1+x_0\times 2^0+0\times 2^{-1})$. 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^n$.

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.

The first partial product can be written as $123\times 6\times {10}^0$ = 738. The second is $123\times 5\times {10}^1=6150$, and the third is $123\times 4\times {10}^2=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 14 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. This results in an algorithm with $O(n)$ complexity, 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 circuits, which are very fast, but require a large number of transistors and consume a great deal of power.

Example 14

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}_2\times {11}_2={1001}_2$. 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.

To multiply two n bit numbers, you must be able to add two 2n bit numbers. Adding 128 bit numbers requires two add instructions and the carry from the least-significant 64 bits must be added to the sum of the most-significant 64 bits. AArch64 provides a convenient way to perform the add with carry. Assume we have two 128 bit numbers, x and y. We have x in , and y in , , 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 an AArch64 processor. The first instruction adds the two least-significant words together and sets (or clears) the carry bit and other flags in the register. The second instruction adds the two most significant words along with the carry bit. This technique can be extended to add integers with any number of bits.

On an AArch64 processor, the algorithm to multiply two 64-bit unsigned integers is very efficient. Listing 7.2 shows one possible algorithm for multiplying two 64-bit numbers to obtain a 128-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 64-bit result, we do not need to perform 128-bit addition. This significantly simplifies the code, as shown in Listing 7.3.

7.2.3 Signed multiplication

Consider the two multiplication problems shown in Fig. 7.1 and Fig. 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 CPU's 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.

Example 16

Signed multiplication using unsigned math.

7.2.4 Multiplication of a variable by a constant

If x or y is a small constant, then we don't need the loop. We can directly translate the multiplication into a sequence of shift and add operations. This will result in much more efficient code than the general algorithm. For small constants, this method is often faster than using a hardware multiply instruction. 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}_{10}={1010}_2$, 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}_{10}={1011}_2$, 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}_{10}={1111101000}_2$. It looks like we need 1 shift plus 5 add/shift operations, or 6 add/shift operations. With a little thought, we can reduce the number of operations, 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. However, on most processors, it is often more efficient to use the shift, add, and subtract operations when multiplying by a small constant. The AArch64 processors have a particularly powerful hardware multiplier. They can typically perform multiplication with a 64-bit result in 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 AArch64 processor to multiply by a constant requires loading the constant into a register before performing the multiply. Therefore, if the multiplication can be performed using two or fewer shift, add, and/or subtract instructions, then it will be equal to or better than using the multiply instruction.

7.2.5 Multiplying large numbers

Consider the method used for multiplying two digit numbers in base ten, using only the one-digit multiplication tables. Fig. 7.3 shows how a two digit number $a=a_1\times {10}^1+a_0\times {10}^0$ is multiplied by another two digit number $b=b_1\times {10}^1+b_0\times {10}^0$ 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 eight-bit numbers, then they are also two-digit hexadecimal numbers. In other words eight 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 eight-bit result from two four-bit inputs, the technique shown above can then be used to multiply two eight-bit numbers using only four-bit multiplication operations.

Carrying this one step further, suppose we are given two sixteen-bit numbers, but our computer only supports multiplying eight bits at a time and producing a sixteen bit result. We can consider each sixteen 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 technique can be extended to perform multiplication with any number of bits, even with limited hardware multiplication instructions.

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^n$. However, care must be taken to ensure that an arithmetic shift is used if the dividend is a signed two's complement number, and a logical shift is used if the dividend 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: The first phase is to shift the divisor left until it is greater than the dividend, and count the number of shifts. The second phase is to repeatedly shift the divisor back to the right and subtract whenever possible. Fig. 7.5 shows the algorithm in more detail. Before we introduce the AArch64 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, on 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 will be in the registers 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 AArch64 assembly code to implement this version of the division algorithm for 64-bit numbers, and the counting method for 128-bit numbers.

7.3.3 Division by a constant

In general, division is slow. AArch64 processors provide a hardware divide instruction which requires multiple clock cycles to produce a result, depending on the size of the operands. Some older ARMv7 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:

$x÷c=x\times \frac{1}{c}.$

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^n$), we can rewrite Eq. (7.1) as follows:

$x÷c=x\times \frac{2^n}{c}\times 2^{-n}.$

Recall that, in binary, multiplying by $2^n$ is the same as shifting left by n bits, while multiplying by $2^{-n}$ 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

$m=\frac{2^n}{c}.$

We can rewrite Eq. (7.2) as:

$x÷c=x\times m\times 2^{-n}.$

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}_2\ge m\ge {01000000}_2$. 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\times 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 ${\mathrm{\text{5A}}}_{16}$. 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}_{10}÷{23}_{10}$ 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}_2=4_{10}$. If the modulus is required, it can be calculated as $101\mathrm{mod}23=101-(4\times 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

$n=p+\lfloor {\log }_{2}c\rfloor -1,$

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

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

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

$n=16+\lfloor {\log }_{2}33\rfloor -1=16+\lfloor 5.044394\rfloor -1=16+5-1=20,$

and then we compute m as

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

Therefore, multiplying a 16 bit number by ${\mathrm{\text{7C20}}}_{16}$ and then shifting right 20 bits is equivalent to dividing by 33.

Example 17

Division by constant 193.

Example 17 shows how to calculate m and n for division by 193. On the AArch64 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.

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={\mathrm{\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^{24}(2^{6}x+2^{4}x+2^{3}x+2^{0}x)+2^{13}(2^{6}x+2^{4}x+2^{3}x+2^{0}x)+2^2(2^{6}x+2^{4}x+2^{3}x+2^{0}x)+2^{0}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:

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 dividend by an n digit divisor and producing a 2n digit quotient and an n digit remainder. for example, the AArch64 processor is capable of dividing a 64-bit dividend by a 64-bit divisor, producing a 64-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 dividend by a 32-bit divisor.

We have seen that, given a divide operation capable of dividing an n digit dividend by an n digit divisor, 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.