Page 220 - ARM 64 Bit Assembly Language

208 Chapter 7

n
Recall that, in binary, multiplying by 2 is the same as shifting left by n bits, while multiply-
ingby2 −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

2 n
m = . (7.3)
c

We can rewrite Eq. (7.2)as:

x ÷ c = x × m × 2 −n . (7.4)

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.
2 n
Ourfirsttaskistofind m = such that 01111111 2 ≥ m ≥ 01000000 2 .Inother words, we
c
want to find the value of n where the most significant bit of m is zero, and the next most sig-
nificant bit of m is one. If we choose n = 11, then

2 11
m = ≈ 89.0434782609.
23

Rounding to the nearest integer gives m = 89. In 8 bits, m is 01011001 2 or 59 16 .Wenowhave
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 num-
ber would be changed from 59 16 to 5A 16 . When implementing this technique for finding the
reciprocal, the programmer should always verify that the results are correct for all input val-
ues. 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: