8.1.1 Arbitrary Base to Decimal

The procedure for converting fractions from a given base b into base ten is very similar to the procedure used for integers. The only difference is that the digit to the left of the radix point is weighted by b⁰ and the exponents become increasingly negative for each digit right of the radix point. The basic procedure is the same for any base b. For example, the value 101.0101₂ can be converted to base ten by expanding it as follows:

$\begin{array}{ll}\hfill & 1\times 2^2+0\times 2^1+1\times 2^0+0\times 2^{-1}+1\times 2^{-2}+0\times 2^{-3}+1\times 2^{-4}\hfill \\ \hfill & =4+0+1+0+\frac{1}{4}+0+\frac{1}{16}\hfill \\ \hfill & =5.3125_{10}\hfill \end{array}$

Likewise, the hexadecimal fraction 4F2.9A0 can be converted to base ten by expanding it as follows:

$\begin{array}{ll}\hfill & 4\times 16^2+15\times 16^1+2\times 16^0+9\times 16^{-1}+10\times 16^{-2}+0\times 16^{-3}\hfill \\ \hfill & =1024+240+2+\frac{9}{16}+\frac{10}{256}+\frac{0}{4096}\hfill \\ \hfill & =1266.6015625_{10}\hfill \end{array}$

8.1.2 Decimal to Arbitrary Base

When converting from base ten into another base, the integer and fractional parts are treated separately. The base conversion for the integer part is performed in exactly the same way as in Section 1.3.2, using repeated division by the base b. The fractional part is converted using repeated multiplication. For example, to convert the decimal value 5.6875₁₀ to a binary representation:

1. Convert the integer portion, 5₁₀ into its binary equivalent, 101₂.

2. Multiply the decimal fraction by two. The integer part of the result is the first binary digit to the right of the radix point.
Because x = 0.6875 × 2 = 1.375, the first binary digit to the right of the point is a 1. So far, we have 5.625₁₀ = 101.1₂

3. Multiply the fractional part of x by 2 once again.
Because x = 0.375 × 2 = 0.75, the second binary digit to the right of the point is a 0. So far, we have 5.625₁₀ = 101.10₂

4. Multiply the fractional part of x by 2 once again.
Because x = 0.75 × 2 = 1.50, the third binary digit to the right of the point is a 1. So now we have 5.625 = 101.101

5. Multiply the fractional part of x by 2 once again.
Because x = 0.5 × 2 = 1.00, the fourth binary digit to the right of the point is a 1. So now we have 5.625 = 101.1011

6. Since the fractional part is now zero, we know that all remaining digits will be zero.

The procedure for obtaining the fractional part can be accomplished easily using a tabular method, as shown below:

Putting it all together, 5.6875₁₀ = 101.1011₂. After converting a fraction from base 10 into another base, the result should be verified by converting back into base 10. The results from the previous example can be expanded as follows:

$\begin{array}{ll}\hfill & 1\times 2^2+0\times 2^1+1\times 2^0+1\times 2^{-1}+0\times 2^{-2}+1\times 2^{-3}+1\times 2^{-4}\hfill \\ \hfill & =4+0+1+\frac{1}{2}+0+\frac{1}{8}+\frac{1}{16}\hfill \\ \hfill & =5.6875_{10}\hfill \end{array}$

Converting decimal fractions to base sixteen is accomplished in a very similar manner. To convert 842.234375₁₀ into base 16, we first convert the integer portion by repeatedly dividing by 16 to yield 34A. We then repeatedly multiply the fractional part, extracting the integer portion of the result each time as shown in the table below:

In the second line, the integer part is 12, which must be replaced with a hexadecimal digit. The hexadecimal digit for 12₁₀ is C, so the fractional part is 3C. Therefore, 842.234375₁₀ =34A.3C₁₆ The result is verified by converting it back into base 10 as follows:

$\begin{array}{ll}\hfill & 3\times 16^2+4\times 16^1+10\times 16^0+3\times 16^{-1}+12\times 16^{-2}\hfill \\ \hfill & =768+64+10+\frac{3}{16}+\frac{12}{256}\hfill \\ \hfill & =842.234375_{10}\hfill \end{array}$

Implications

Theorem 8.2.1 implies that any binary fraction can be expressed exactly as a decimal fraction, but Theorem 8.2.2 implies that there are decimal fractions which cannot be expressed exactly in binary. Every fraction (when expressed in lowest terms) which has a non-zero power of five in its denominator cannot be represented in binary with a finite number of bits. Another implication is that some fractions cannot be expressed exactly in either binary or decimal. For example, let B = 30 = 2 * 3 * 5. Then any number with denominator $2^{k_1}{3}^{k_2}{5}^{k_3}$ terminates in base 30. However if k₂≠0, then the fraction will terminate in neither base two nor base ten, because three is not a prime factor of ten or two.

Another implication of the theorem is that the more prime factors we have in our base, the more fractions we can express exactly. For instance, the smallest base that has two, three, and five as prime factors is base 30. Using that base, we can exactly express fractions in radix notation that cannot be expressed in base ten or in base two with a finite number of digits. For example, in base 30, the fraction $\frac{11}{15}$ will terminate after one division since 15 = 3¹5¹. To see what the number will look like, let us extend the hexadecimal system of using letters to represent digits beyond 9. So we get this chart for base 30:

$\begin{array}{l}\hfill \begin{array}{ccccc}{0}_{10}\to 0_{30}& 1_{10}\to 1_{30}& 2_{10}\to 2_{30}& 3_{10}\to 3_{30}& 4_{10}\to 4_{30}\\ 5_{10}\to 5_{30}& 6_{10}\to 6_{30}& 7_{10}\to 7_{30}& 8_{10}\to 8_{30}& 9_{10}\to 9_{30}\\ 10_{10}\to {\text{A}}_{30}& 11_{10}\to {\text{B}}_{30}& 12_{10}\to {\text{C}}_{30}& 13_{10}\to {\text{D}}_{30}& 14_{10}\to {\text{E}}_{30}\\ 15_{10}\to {\text{F}}_{30}& 16_{10}\to {\text{G}}_{30}& 17_{10}\to {\text{H}}_{30}& 18_{10}\to {\text{I}}_{30}& 19_{10}\to {\text{J}}_{30}\\ 20_{10}\to {\text{K}}_{30}& 21_{10}\to {\text{L}}_{30}& 22_{10}\to {\text{M}}_{30}& 23_{10}\to {\text{N}}_{30}& 24_{10}\to {\text{O}}_{30}\\ 25_{10}\to {\text{P}}_{30}& 26_{10}\to {\text{Q}}_{30}& 27_{10}\to {\text{R}}_{30}& 28_{10}\to {\text{S}}_{30}& 29_{10}\to {\text{T}}_{30}\end{array}\end{array}$

Since $\frac{11}{15}=\frac{22}{30}$, the fraction can be expressed precisely as 0.M₃₀. Likewise, the fraction $\frac{13}{45}$ is $0.2{\overline{8}}_{10}$ but terminates in base 30. Since 45 = 3³5¹, this number will have three or fewer digits following the radix point. To compute the value, we will have to raise it to higher terms. Using 30² as the denominator gives us:

$\begin{array}{ll}\hfill \frac{13}{45}& =\frac{260}{900}\hfill \end{array}$

Now we can convert it to base 30 by repeated division. $\frac{260}{30}=8$ with remainder 20. Since 20 < 30, we cannot divide again. Therefore, $\frac{13}{45}$ in base 30 is 0.8K.

Although base 30 can represent all fractions that can be expressed in bases two and ten, there are still fractions that cannot be represented in base 30. For example, $\frac{1}{7}$ has the prime factor seven in its denominator, and therefore will only terminate in bases were seven is a prime factor of the base. The fraction $\frac{1}{7}$ will terminate in base 7, base 14, base 21, base 42 and many others, but not in base 30. Since there are an infinite number of primes, no number system is immune from this problem. No matter what base the computer works in, there are fractions that cannot be expressed exactly with a finite number of digits. Therefore, it is incumbent upon programmers and hardware designers to be aware of round-off errors and take appropriate steps to minimize their effects.

For example, there is no reason why the hardware clocks in a computer should work in base ten. They can be manufactured to measure time in base two. Instead of counting seconds in tenths, hundredths or thousandths, they could be calibrated to measure in fourths, eighths, sixteenths, 1024ths, etc. This would eliminate the round-off error problem in keeping track of time.

8.3.1 Interpreting Fixed-Point Numbers

Each fixed-point binary number has three important parameters that describe it:

1. whether the number is signed or unsigned,

2. the position of the radix point in relation to the right side of the sign bit (for signed numbers) or the position of the radix point in relation to the most significant bit (for unsigned numbers), and

3. the number of fractional bits stored.

Unsigned fixed-point numbers will be specified as U(i,f), where i is the position of the radix point in relation to the left side of the most significant bit, and f is the number of bits stored in the fractional part.

For example, U(10,6) indicates that there are six bits of precision in the fractional part of the number, and the radix point is ten bits to the right of the most significant bit stored. The layout for this number is shown graphically as:

where i is an integer bit and f is a fractional bit. Very small numbers with no integer part may have a negative i. For example, U(−8,16) specifies an unsigned number with no integer part, eight leading zero bits which are not actually stored, and 16 bits of fractional precision. The layout for this number is shown graphically as:

Likewise, signed fixed-point numbers will be specified using the following notation: S(i,f), where i is the position of the radix point in relation to the right side of the sign bit, and f is the number of fractional bits stored. As with integer two’s-complement notation, the sign bit is always the leftmost bit stored. For example, S(9,6) indicates that there are six bits in the fractional part of the number, and the radix point is nine bits to the right of the sign bit. The layout for this number is shown graphically as:

where i is an integer bit and f is a fractional bit. Very small numbers with no integer part may have a negative i. For example, S(−7,16) specifies a signed number with no integer part, six leading sign bits which are not actually stored, a sign bit that is stored and 15 bits of fraction. The layout for this number is shown graphically as:

Note that the “hidden” bits in a signed number are assumed to be copies of the sign bit, while the “hidden” bits in an unsigned number are assumed to be zero.

The following figure shows an unsigned fixed-point number with seven bits in the integer part and nine bits in the fractional part. It is a U(7,9) number. Note that the total number of bits is 7 + 9 = 16

The value of this number in base 10 can be computed by summing the values of each non-zero bit as follows:

$\begin{array}{ll}\hfill & 2^{13-9}+2^{11-9}+2^{10-9}+2^{9-9}+2^{5-9}+2^{3-9}+2^{1-9}+2^{0-9}\hfill \\ \hfill & =2^4+2^2+2^1+2^0+2^{-4}+2^{-6}+2^{-8}+2^{-9}\hfill \\ \hfill & =16+4+2+1+\frac{1}{16}+\frac{1}{64}+\frac{1}{256}+\frac{1}{512}\hfill \\ \hfill & =23.083984375_{10}\hfill \end{array}$

Likewise, the following figure shows a signed fixed-point number with nine bits in the integer part and six bits in the fractional part. It is as S(9,6) number. Note that the total number of bits is 9 + 6 + 1 = 16.

The value of this number in base 10 can be computed by summing the values of each non-zero bit as follows:

$\begin{array}{ll}\hfill & 2^{13-6}+2^{11-6}+2^{10-6}+2^{9-6}+2^{5-6}+2^{3-6}+2^{1-6}+2^{0-6}\hfill \\ \hfill & =2^7+2^5+2^4+2^3+2^{-1}+2^{-3}+2^{-5}+2^{-6}\hfill \\ \hfill & =128+32+16+8+\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\frac{1}{64}\hfill \\ \hfill & =184.671875_{10}\hfill \end{array}$

Note that in the above two examples, the pattern of bits are identical. The value of a number depends upon how it is interpreted. The notation that we have introduced allows us to easily specify exactly how a number is to be interpreted. For signed values, if the first bit is non-zero, then the two’s complement should be taken before the number is evaluated. For example, the following figure shows an S(8,7) number that has a negative value.

The value of this number in base 10 can be computed by taking the two’s complement, summing the values of the non-zero bits, and adding a negative sign to the result. The two’s complement of 1011010101111010 is 0100101010000101 + 1 = 0100101010000110. The value of this number is:

$\begin{array}{ll}\hfill & -\left(2^{14-7}+2^{11-7}+2^{9-7}+2^{7-7}+2^{2-7}+2^{1-7}\right)\hfill \\ \hfill & =-\left(2^7+2^4+2^2+2^0+2^{-5}+2^{-6}\right)\hfill \\ \hfill & =-\left(128+16+4+1+\frac{1}{32}+\frac{1}{64}\right)\hfill \\ \hfill & =-149.046875_{10}\hfill \end{array}$

For a final example we will interpret this bit pattern as an S(−5,16). In that format, the layout is:

The value of this number in base ten can be computed by taking the two’s complement, summing the values of the non-zero bits, and adding a negative sign to the result. The two’s complement is:

The value of this number interpreted as an S(−5,16) is:

$-\left(2^{-6}+2^{-9}+2^{-11}+2^{-13}+2^{-18}+2^{-19}\right)=-0.0181941986083984375$

8.3.2 Q Notation

Fixed-point number formats can also be represented using Q notation, which was developed by Texas Instruments. Q notation is equivalent to the S/U format used in this book, except that the integer portion is not always fully specified. In general, Q formats are specified as Qm, n where m is the number of integer bits, and n is the number of fractional bits. If a fixed word size w is being used then m may be omitted, and is assumed to be w − n. For example, a Q10 number has 10 fractional bits, and the number of integer bits is not specified, but is assumed to be the number of bits required to complete a word of data. A Q2,4 number has two integer bits and four fractional bits in a 6-bit word. There are two conflicting conventions for dealing with the sign bit. In one convention, the sign bit is included as part of m, and in the other convention, it is not. When using Q notation, it is important to state which convention is being used. Additionally, a U may be prefixed to indicate an unsigned value. For example UQ8.8 is equivalent to U(8,8), and Q7,9 is equivalent to S(7,9).

8.3.3 Properties of Fixed-Point Numbers

Once the decision has been made to use fixed-point calculations, the programmer must make some decisions about the specific representation of each fixed-point variable. The combination of size and radix will affect several properties of the numbers, including:

Precision: the maximum number of non-zero bits representable,

Resolution: the smallest non-zero magnitude representable,

Accuracy: the magnitude of the maximum difference between a true real value and its approximate representation,

Range: the difference between the largest and smallest number that can be represented, and

Dynamic range: the ratio of the maximum absolute value to the minimum positive absolute value representable.

Given a number specified using the notation introduced previously, we can determine its properties. For example, an S(9,6) number has the following properties:

Precision: P = 16 bits

Resolution: R = 2⁻⁶ = 0.015625

Accuracy: $A=\frac{R}{2}=0.0078125$

Range: Minimum value is 1000000000.000000 = −512 Maximum value is 0111111111.111111 = 1023.9921875 Range is G = 1023.9921875 + 512 = 1535.9921875

Dynamic range: For a signed fixed-point rational representation, S(i,f), the dynamic range is

$\begin{array}{l}\hfill D=2\times \frac{2^i}{2^{-f}}=2^{i+f+1}=2^P.\end{array}$

Therefore, the dynamic range of an S(9,6) is 2¹⁶ = 65536.

Being aware of these properties, the programmer can select fixed-point representations that fit the task that they are trying to solve. This allows the programmer to strive for very efficient code by using the smallest fixed-point representation possible, while still guaranteeing that the results of computations will be within some limits for error tolerance.

8.4.1 Fixed-Point Addition and Subtraction

Fixed-point addition and subtraction work exactly like their integer counterparts. Fig. 8.1 gives some examples of fixed-point addition with signed numbers. Note that in each case, the numbers are aligned so that they have the same number of bits in their fractional part. This requirement is the only difference between integer and fixed-point addition. In fact, integer arithmetic is just fixed-point arithmetic with no bits in the fractional part. The arithmetic that was covered in Chapter 7 was fixed-point arithmetic using only S(i,0) and U(i,0) numbers. Now we are simply extending our knowledge to deal with numbers where f≠0. There are some rules which must be followed to ensure that the results are correct. The rules for subtraction are the same as the rules for addition. Since we are using two’s complement math, subtraction is performed using addition.

Suppose we want to add an S(7,8) number to an S(7,4) number. The radix points are at different locations, so we cannot simply add them. Instead, we must shift one of the numbers, changing its format, until the radix points are aligned. The choice of which one to shift depends on what format we desire for the result. If we desire eight bits of fraction in our result, then we would shift the S(7,4) left by four bits, converting it into an S(7,8). With the radix points aligned, we simply use an integer addition operation to add the two numbers. The result will have it’s radix point in the same location as the two numbers being added.

8.4.2 Fixed Point Multiplication

Recall that the result of multiplying an n bit number by an m bit number is an n + m bit number. In the case of fixed-point numbers, the size of the fractional part of the result is the sum of the number of fractional bits of each number, and the total size of the result is the sum of the total number of bits in each number. Consider the following example where two U(5,3) numbers are multiplied together:

The result is a U(10,6) number. The number of bits in the result is the sum of all of the bits of the multiplicand and the multiplier. The number of fractional bits in the result is the sum of the number of fractional bits in the multiplicand and the multiplier. There are three simple rules to predict the resulting format when multiplying any two fixed-point numbers.

Unsigned Multiplication The result of multiplying two unsigned numbers U(i₁,f₁) and U(i₂,f₂) is a U(i₁ + i₂,f₁ + f₂) number.

Mixed Multiplication The result of multiplying a signed number S(i₁,f₁) and an unsigned number U(i₂,f₂) is an S(i₁ + i₂,f₁ + f₂) number.

Signed Multiplication The result of multiplying two signed numbers S(i₁,f₁) and S(i₂,f₂) is an S(i₁ + i₂ + 1,f₁ + f₂) number.

Note that this rule works for integers as well as fixed-point numbers, since integers are really fixed-point numbers with f = 0. If the programmer desires a particular format for the result, then the multiply is followed by an appropriate shift.

Listing 8.1 gives some examples of fixed-point multiplication using the ARM multiply instructions. In each case, the result is shifted to produce the desired format. It is the responsibility of the programmer to know what type of fixed-point number is produced after each multiplication and to adjust the result by shifting if necessary.

8.4.3 Fixed Point Division

Derivation of the rule for determining the format of the result of division is more complicated than the one for multiplication. We will first consider only unsigned division of a dividend with format U(i₁,f₁) by a divisor with format U(i₂,f₂).

Results of fixed point division

Consider the results of dividing two fixed-point numbers, using integer operations with limited precision. The value of the least significant bit of the dividend N is $2^{-f_i}$ and the value of the least significant bit of the divisor D is $2^{-f_2}$. In order to perform the division using integer operations, it is necessary to multiply N by $2^{f_i}$ and multiply D by $2^{f_2}$ so that both numbers are integers. Therefore, the division operation can be written as:

$\begin{array}{l}\hfill Q=\frac{N\times 2^{f_1}}{D\times 2^{f_2}}=\frac{N}{D}\times 2^{f_1-f_2}.\end{array}$

Note that no multiplication is actually performed. Instead, the programmer mentally shifts the radix point of the divisor and dividend, then computes the radix point of the result. For example, given two U(5,3) numbers, the division operation is accomplished by converting them both to integers, performing the division, then computing the location radix point:

$\begin{array}{l}\hfill Q=\frac{N\times 2^3}{D\times 2^3}=\frac{N}{D}\times 2^0.\end{array}$

Note that the result is an integer. If the programmer wants to have some fractional bits in the result, then the dividend must be shifted to the left before the division is performed.

If the programmer wants to have f_q fractional bits in the quotient, then the amount that the dividend must be shifted can easily be computed as

$\begin{array}{l}\hfill s=f_q+f_1-f_2.\end{array}$

For example, suppose the programmer wants to divide 01001.011 stored as a U(28,3) by 00011.110 which is also stored as a U(28,3), and wishes to have six fractional bits in the result. The programmer would first shift 01001.011 to the left by six bits, then perform the division and compute the position of the radix in the result as shown:

Since the divisor may be between zero and one, the quotient may actually require more integer bits than there are in the dividend. Consider that the largest possible value of the dividend is $N_{\max }=2^{i_1}-2^{-f_1}$, and the smallest positive value for the divisor is $D_{min}=2^{-f_2}$. Therefore, the maximum quotient is given by:

$\begin{array}{l}\hfill Q_{max}=\frac{2^{i_1}-2^{-f_1}}{2^{-f_2}}=2^{i_1+f_2}-2^{f_1-f_2}.\end{array}$

Taking the limit of the previous equation,

$\begin{array}{l}\hfill \underset{f_1-f_2\to -\infty }{lim}{Q}_{max}=2^{i_1+f_2},\end{array}$

provides the following bound on how many bits are required in the integer part of the quotient:

$\begin{array}{l}\hfill Q_{max}<2^{i_1+f_2}.\end{array}$

Therefore, in the worst case, the quotient will require i₁ + f₂ integer bits. For example, if we divide a U(3,5), a = 111.11111 = 7.96875₁₀, by a U(5,3), b = 00000.001 = 0.125₁₀, we end up with a U(6,2)q = 111111.11 = 63.75₁₀.

The same thought process can be used to determine the results for signed division as well as mixed division between signed and unsigned numbers. The results can be reduced to the following three rules:

Unsigned Division The result of dividing an unsigned fixed-point number U(i₁,f₁) by an unsigned number U(i₂,f₂) is a U(i₁ + f₂,f₁ − f₂) number.

Mixed Division The result of dividing two fixed-point numbers where one of them is signed and the other is unsigned is an S(i₁ + f₂,f₁ − f₂) number.

Signed Division The result of dividing two signed fixed-point numbers is an S(i₁ + f₂ + 1,f₁ − f₂) number.

Consider the results when a U(2,3), a = 00000.001 = 0.125₁₀ is divided by a U(4,1), b = 1000.0 = 8.0₁₀. The quotient is q = 0.000001, which requires six bits in the fractional part. However, if we simply perform the division, then according to the rules shown above, the result will be a U(8,−2). There is no such thing as a U(8,−2), so the result is meaningless.

When f₂ > f₁, blindly applying the rules will result in a negative fractional part. To avoid this, the dividend can be shifted left so that it has at least as many fractional bits as the divisor. This leads to the following rule: If f₂ > f₁ then convert the divisor to an S(i₁,x), where x ≥ f₂, then apply the appropriate rule. For example, dividing an S(5,2) by a U(3,12) would result in an S(17,−10). But shifting the S(5,2) 16 bits to the left will result in an S(5,18), and dividing that by a U(3,12) will result in an S(17,6).

8.4.4 Division by a Constant

Section 7.3.3 introduced the idea of converting division by a constant into multiplication by the reciprocal of that constant. In that section it was shown that by pre-multiplying the reciprocal by a power of two (a shift operation), then dividing the final result by the same power of two (a shift operation), division by a constant could be performed using only integer operations with a more efficient multiply replacing the (usually) very slow divide.

This section presents an alternate way to achieve the same results, by treating division by an integer constant as an application of fixed-point multiplication. Again, the integer constant divisor is converted into its reciprocal, but this time the process is considered from the viewpoint of fixed-point mathematics. Both methods will achieve exactly the same results, but some people tend to grasp the fixed-point approach better than the purely integer approach.

When writing code to divide by a constant, the programmer must strive to achieve the largest number of significant bits possible, while using the shortest (and most efficient) representation possible. On modern computers, this usually means using 32-bit integers and integer multiply operations which produce 64-bit results. That would be extremely tedious to show in a textbook, so the principals will be demonstrated here using 8-bit integers and an integer multiply which produces a 16-bit result.

Division by constant 23

Suppose we want efficient code to calculate x ÷ 23 using only 8-bit signed integer multiplication. The reciprocal of 23, in binary, is

$\begin{array}{l}\hfill R=\frac{1}{23}=0.0000101100100001011{\dots }_2.\end{array}$

If we store R as an S(1,11), it would look like this:

Note that in this format, the reciprocal of 23 has five leading zeros. We can store R in eight bits by shifting it left to remove some of the leading zeros. Each shift to the left changes the format of R. After removing the first leading zero bit, we have:

After removing the second leading zero bit, we have:

After removing the third leading zero bit, we have:

Note that the number in the previous format has a “hidden” bit between the radix point and the sign bit. That bit is not actually stored, but is assumed to be identical to the sign bit. Removing the fourth leading zero produces:

The number in the previous format has two “hidden” bits between the radix point and the sign bit. Those bits are not actually stored, but are assumed to be identical to the sign bit. Removing the fifth leading zero produces:

We can only remove five leading zero bits, because removing one more would change the sign bit from 0 to 1, resulting in a completely different number. Note that the final format has three “hidden” bits between the radix point and the sign bit. These bits are all copies of the sign bit. It is an S(−4,8) number because the sign is four bits to the right of the radix point (resulting in the three “hidden” bits). According to the rules of fixed-point multiplication given earlier, an S(7,0) number x multiplied by an S(−4,8) number R will yield an S(4,8) number y. The value y will be $2^3\times \frac{x}{23}$ because we have three “hidden” bits to the right of the radix point. Therefore,

$\begin{array}{l}\hfill \frac{x}{23}=R\times x\times 2^{-3},\end{array}$

indicating that after the multiplication, we must shift the result right by three bits to restore the radix. Since $\frac{1}{23}$ is positive, the number R must be increased by one to avoid round-off error. Therefore, we will use R + 1 = 01011010 = 90₁₀ in our multiply operation. To calculate y = 101₁₀ ÷ 23₁₀, we can multiply and perform a shift as follows:

Because our task is to implement integer division, everything to the right of the radix point can be immediately discarded, keeping only the upper eight bits as the integer portion of the result. The integer portion, 100011₂, shifted right three bits, is 100₂ = 4₁₀. If the modulus is required, it can be calculated as: 101 − (4 × 23) = 9. Some processors, such as the Motorola HC11, have a special multiply instruction which keeps only the upper half of the result. This method would be especially efficient on that processor. Listing 8.2 shows how the 8-bit division code would be implemented in ARM assembly. Listing 8.3 shows an alternate implementation which uses shift and add operations rather than a multiply.

Division by constant −50

The procedure is exactly the same for dividing by a negative constant. Suppose we want efficient code to calculate $\frac{x}{-50}$ using 16-bit signed integers. We first convert $\frac{1}{50}$ into binary:

$\begin{array}{l}\hfill \frac{1}{50}=0.00000\overline{10100011110}\end{array}$

The two’s complement of $\frac{1}{50}$ is

$\begin{array}{l}\hfill \frac{1}{-50}=1.11111\overline{01011100001}\end{array}$

We can represent $\frac{1}{-50}$ as the following S(1,21) fixed-point number:

Note that the upper seven bits are all one. We can remove six of those bits and adjust the format as follows. After removing the first leading one, the reciprocal is:

Removing another leading one changes the format to:

On the next step, the format is:

Note that we now have a “hidden” bit between the radix point and the sign bit. The hidden bit is not actually part of the number that we store and use in the computation, but it is assumed to be the same as the sign bit.

After three more leading ones are removed, the format is:

Note that there are four “hidden” bits between the radix point and the sign. Since the reciprocal $\frac{1}{-50}$ is negative, we do not need to round by adding one to the number R. Therefore, we will use R = 1010111000010101₂ = AE15₁₆ in our multiply operation.

Since we are using 16-bit integer operations, the dividend, x, will be an S(15,0). The product of an S(15,0) and an S(−5,16) will be an S(11,16). We will remove the 16 fractional bits by shifting right. The four “hidden” bits indicate that the result must be shifted an additional four bits to the right, resulting in a total shift of 20 bits. Listing 8.4 shows how the 16-bit division code would be implemented in ARM assembly.

8.5.1 IEEE 754 Half-Precision

The half-precision format gives a 16-bit encoding for fractional numbers with a small range and low precision. There are situations where this format is adequate. If the computation is being performed on a very small machine, then using this format may result in significantly better performance than could be attained using one of the larger IEEE formats. However, in most situations, the programmer can achieve better performance and/or precision by using a fixed-point representation. The format is as follows:

• The Significand (a.k.a. “Mantissa”) is stored using a sign-magnitude coding, with bit 15 being the sign bit.

• The exponent is an excess-15 number. That is, the number stored is 15 greater than the actual exponent.

• There are 10 bits of significand, but there are 11 bits of significand precision. There is a “hidden” bit, m₁₀, between m₉ and e₀. When a number is stored in this format, it is shifted until its leftmost non-zero bit is in the hidden bit position, and the hidden bit is not actually stored. The exception to this rule is when the number is zero or very close to zero. The radix point is assumed to be between the hidden bit and the first bit stored. The radix point is then shifted by the exponent.

Table 8.1 shows how to interpret IEEE 754 Half-Precision numbers. The exponents 00000 and 11111 have special meaning. The value 00000 is used to represent zero and numbers very close to zero, and the exponent value 11111 is used to represent infinity and NaN. NaN, which is the abbreviation for not a number, is a value representing an undefined or unrepresentable value. One way to get NaN as a result is to divide infinity by infinity. Another is to divide zero by zero. The NaN value can indicate that there is a bug in the program, or that a calculation must be performed using a different method.

Table 8.1

Format for IEEE 754 half-precision

Exponent	Significand = 0	Significand≠0	Equation
00000	± 0	subnormal	− 1sign × 2−14 × 0.significand
00001 …11110	normalized value		− 1sign × 2exp−15 × 1.significand
11111	$\pm \infty$	NaN

Subnormal means that the value is too close to zero to be completely normalized. The minimum strictly positive (subnormal) value is 2⁻²⁴ ≈ 5.96 × 10⁻⁸. The minimum positive normal value is 2⁻¹⁴ ≈ 6.10 × 10⁻⁵. The maximum exactly representable value is (2 − 2⁻¹⁰) × 2¹⁵ = 65504.

Examples

The following bit value:

represents

$\begin{array}{ll}\hfill +1.1000101011\times 2^{01011-01111}& =1.1000101011\times 2^{-4}=0.00011000101011\hfill \\ \hfill & \approx 0.09637.\hfill \end{array}$

The following bit value:

represents

$\begin{array}{ll}\hfill -1.0000100101\times 2^{11001-01111}& =-1.0000100101\times 2^{10}=-10000100101.0\hfill \\ \hfill & =-1061_{10}.\hfill \end{array}$

8.5.2 IEEE 754 Single-Precision

The single precision format provides a 23-bit mantissa and an 8-bit exponent, which is enough to represent a reasonably large range with reasonable precision. This type can be stored in 32 bits, so it is relatively compact. At the time that the IEEE standards were defined, most machines used a 32-bit word, and were optimized for moving and processing data in 32-bit quantities. For many applications this format represents a good trade-off between performance and precision.

8.5.3 IEEE 754 Double-Precision

The double-precision format was designed to provide enough range and precision for most scientific computing requirements. It provides a 10-bit exponent and a 53-bit mantissa. When the IEEE 754 standard was introduced, this format was not supported by most hardware. That has changed. Most modern floating point hardware is optimized for the IEEE 754 double-precision standard, and most modern processors are designed to move 64-bit or larger quantities. On modern floating-point hardware, this is the most efficient representation.

However, processing large arrays of double-precision data requires twice as much memory, and twice as much memory bandwidth, as single-precision.

8.5.4 IEEE 754 Quad-Precision

The IEEE 754 Quad-Precision format was designed to provide enough range and precision for very demanding applications. It provides a 14-bit exponent and a 116-bit mantissa. This format is still not supported by most hardware. The first hardware floating point unit to support this format was the SPARC V8 architecture. As of this writing, the popular Intel x86 family, including the 64-bit versions of the processor, do not have hardware support for the IEEE 754 quad-precision format. On modern high-end processors such as the SPARC, this may be an efficient representation. However, for mid-range processors such as the Intel x86 family and the ARM, this format is definitely out of their league.

8.6.1 Floating Point Addition and Subtraction

The steps required for addition and subtraction of floating point numbers is the same, regardless of the specific format. The steps for adding or subtracting to floating point numbers a and b are as follows:

1. Extract the exponents E_a and E_b.

2. Extract the significands M_a and M_b. and convert them into 2’s complement numbers, using the signs S_a and S_b.

3. Shift the significand with the smaller exponent right by |E_a − E_b|.

4. Perform addition (or subtraction) on the significands to get the significand of the result, M_r. Remember that the result may require one more significant bit to avoid overflow.

5. If M_r is negative, then take the 2’s complement and set S_r to 1. Otherwise set S_r to 0.

6. Shift M_r until the leftmost 1 is in the “hidden” bit position, and add the shift amount to the smaller of the two exponents to form the new exponent E_r.

7. Combine the sign S_r, the exponent E_r, and significand M_r to form the result.

The complete algorithm must also provide for correct handling of infinity and NaN.

8.6.2 Floating Point Multiplication and Division

Multiplication and division of floating point numbers also requires several steps. The steps for multiplication and division of two floating point numbers a and b are as follows:

1. Calculate the sign of the result S_r.

2. Extract the exponents E_a and E_b.

3. Extract the significands M_a and M_b.

4. Multiply (or divide) the significands to form M_r.

5. Add (or subtract) the exponents (in excess-N) to get E_r.

6. Shift M_r until the leftmost 1 is in the “hidden” bit position, and add the shift amount to E_r.

7. Combine the sign S, the exponent E_r, and significand M_r to form the result.

The complete algorithm must also provide for correct handling of infinity and NaN.

8.7.1 Formats for the Powers of x

The numerators in the first nine terms of the Taylor series approximation are: x, x³, x⁵, x⁷, x⁹, x¹¹, x¹³, x¹⁵, and x¹⁷. Given an S(1,30) format for x, we can predict the format for the numerator of each successive term in the Taylor series. If we simply perform successive multiplies, then we would get the following formats for the powers of x:

The middle column in the table shows that the format for x¹⁷ would require 528 bits if all of the fractional bits are retained. Dealing with a number at that level of precision would be slow and impractical. We will, of necessity, need to limit the number of bits used. Since the ARM processor provides a multiply instruction involving two 32-bit numbers, we choose to truncate the numerators to 32 bits. The third column in the table indicates the resulting format for each term if precision is limited to 32 bits.

On further consideration of the Taylor series, we notice that each of the above terms will be divided by a constant. Instead of dividing, we can multiply by the reciprocal of the constant. We will create a similar table holding the formats and constants for the factorial terms. With a bit of luck, the division (implemented as multiplication) in each term will result in a reasonable format for each resulting term.

8.7.2 Formats and Constants for the Factorial Terms

The first term of the Taylor series is $\frac{x}{1!}$, so we can simply skip the division. The second term is $-\frac{x^3}{3!}=x^3\times -\frac{1}{3!}$ and the third term is $\frac{x^5}{5!}=x^5\times \frac{1}{5!}$ We can convert $-\frac{1}{3!}$ to binary as follows:

Multiplication	Result
	Integer	Fraction
$\frac{1}{6}\times 2=\frac{2}{6}$	0	$\frac{2}{6}$
$\frac{2}{6}\times 2=\frac{4}{6}$	0	$\frac{4}{6}$
$\frac{4}{6}\times 2=\frac{8}{6}$	1	$\frac{2}{6}$
$\frac{2}{6}\times 2=\frac{4}{6}$	0	$\frac{4}{6}$
$\frac{8}{6}\times 2=\frac{8}{6}$	1	$\frac{2}{6}$

Since the pattern repeats, we can conclude that $\frac{1}{3!}=0.0{\overline{01}}_2$. Since we need a negative number, we take the two’s complement, resulting in $-\frac{1}{3!}=\dots 111.1{\overline{10}}_2$. Represented as an S(1,30), this would be

Since the first four bits are one, we can remove three bits and store it as:

In hexadecimal, this is AAAAAAAA₁₆.

Performing the same operations, we find that $\frac{1}{5!}$ can be converted to binary as follows:

Multiplication	Result
	Integer	Fraction
$\frac{1}{120}\times 2=\frac{2}{120}$	0	$\frac{2}{120}$
$\frac{2}{120}\times 2=\frac{4}{120}$	0	$\frac{4}{120}$
$\frac{4}{120}\times 2=\frac{8}{120}$	0	$\frac{8}{120}$
$\frac{8}{120}\times 2=\frac{16}{120}$	0	$\frac{16}{120}$
$\frac{16}{120}\times 2=\frac{32}{120}$	0	$\frac{32}{120}$
$\frac{32}{120}\times 2=\frac{64}{120}$	0	$\frac{64}{120}$
$\frac{64}{120}\times 2=\frac{128}{120}$	1	$\frac{8}{120}$

Since the fraction in the seventh row is the same as the fraction in the third row, we know that the table will repeat forever. Therefore, $\frac{1}{5!}=0.000{\overline{0001}}_2$. Since the first six bits to the right of the radix are all zero, we can remove the first five bits. Also adding one to the least significant bit to account for rounding error yields the following S(−6,32):

In hexadecimal, the number to be multiplied is 44444445₁₆. Note that since $\frac{1}{5!}$ is a positive number, the reciprocal was incremented by one to avoid round-off errors. We can apply the same procedure to the remaining terms, resulting in the following table:

Term	Reciprocal Format	Reciprocal Value (Hex)
$-\frac{1}{3!}$	S(−2,32)	AAAAAAAA
$\frac{1}{5!}$	S(−6,32)	44444445
$-\frac{1}{7!}$	S(−12,32)	97F97F97
$\frac{1}{9!}$	S(−18,32)	5C778E96
$-\frac{1}{11!}$	S(−25,32)	9466EA60
$\frac{1}{13!}$	S(−32,32)	5849184F

8.7.3 Putting it All Together

We want to keep as much precision as is reasonably possible for our intermediate calculations. Using 64 bits of precision for all intermediate calculations will give a good trade-off between performance and precision. The integer portion should never require more than two bits, so we choose an S(2,61) as our intermediate representation. If we combine the previous two tables, we can determine what the format of each complete term will be. This is shown in Table 8.2.

Table 8.2

Result formats for each term

	Numerator		Reciprocal			Result
Term	Value	Format	Value	Format	Hex	Format
1	x	S(1,30)	Extend to 64 bits and shift right			S(2,61)
2	x3	S(3,28)	$-\frac{1}{3!}$	S(−2,32)	AAAAAAAA	S(2, 61)
3	x5	S(5,26)	$\frac{1}{5!}$	S(−6,32)	44444444	S(0, 63)
4	x7	S(7,24)	$-\frac{1}{7!}$	S(−12,32)	97F97F97	S(−4, 64)
5	x9	S(9,22)	$\frac{1}{9!}$	S(−18,32)	5C778E96	S(−8, 64)
6	x11	S(11,20)	$-\frac{1}{11!}$	S(−25,32)	9466EA60	S(−13, 64)
7	x13	S(13,18)	$\frac{1}{13!}$	S(−32,32)	5849184F	S(−18, 64)

Note that the formats were truncated to fit in a 64-bit result. We can now see that the formats for the first nine terms of the Taylor series are reasonably similar. They all require exactly 64 bits, and the radix points can be shifted so that they are aligned for addition. In order to make the shifting and adding process easier, we will pre-compute the shift amounts and store them in a look-up table.

Table 8.3 shows the shifts that are necessary to convert each term to an S(2,61) so that it can be added to the running total.

Note that the seventh term contributes very little to the final 32-bit sum which is stored in the upper 32 bits of the running total. We now have all of the information that we need in order to implement the function. Listing 8.7 shows how the sine and cosine function can be implemented in ARM assembly using fixed point computation, and Listing 8.8 shows a main program which prints a table of values and their sine and cosines.

8.7.4 Performance Comparison

In some situations it can be very advantageous to use fixed-point math. For example, when using an ARMv6 or older processor, there may not be a hardware floating point unit available. Table 8.4 shows the CPU time required for running a program to compute the sine function on 10,000,000 random values, using various implementations of the sine function. In each case, the program main() function was written in C. The only difference in the six implementations was the data type (which could be fixed-point, IEEE single precision, or IEEE double precision), and the sine function that was used. The times shown in the table include only the amount of CPU time actually used in the sine function, and do not include the time required for program startup, storage allocation, random number generation, printing results, or program exit. The six implementations are as follows:

32-bit Fixed Point Assembly The sine function is computed using the code shown in Listing 8.7.

32-bit Fixed Point C The sine function is computed using exactly the same algorithm as in Listing 8.7, but it is implemented in C rather than Assembly.

Single Precision Software Float C Sine is computed using the floating point sine function which is provided by the GCC C compiler. The code is compiled for an ARMv6 or earlier processor without hardware floating point support. The C code is written to use IEEE single precision floating point numbers.

Double Precision Software Float C Exactly the same as the previous method, but using IEEE double precision instead of single precision.

Single Precision VFP C Sine is computed using the floating point sine function which is provided by the GCC C compiler. The code is compiled for the ARMv6 or later processor using hardware floating point support. The C code is written to use IEEE single precision floating point numbers.

Double Precision VFP C Same as the previous method, but using IEEE double precision instead of single precision.

Each of the six implementations was compiled both with and without compiler optimizations, resulting in a total of 12 test cases. All cases were run on a standard Raspberry Pi model B with the default CPU clock rate.

From Table 8.4, it is clear that the fixed-point implementation written in assembly beats the code generated by the compiler in every case. The closest that the compiler can get is when it can use the VFP hardware floating point unit and the compiler is run with full optimization. Even in that case the fixed-point assembly implementation is almost 15% faster than the single precision floating point implementation, and has 33% more precision (32 bits versus 24 bits). In the worst case, when a VFP hardware unit is not available, the assembly code beats the compiler by a whopping 638% in speed and 33% in precision for single precision floats, and is 1692% faster than double precision floating point at a cost of 41% in precision. Note that even with floating point hardware support, fixed point in assembly is still 3.44 times as fast as the C compiler code.

Similar results could be obtained on any processor architecture, and any reasonably complex mathematical problem. When developing software for small systems, the developer must weigh the costs and benefits of alternative implementations. For battery powered systems, it is important to realize that choices of hardware and software can affect power consumption even more strongly than computing performance. First, the power used by a system which includes a hardware floating point processor will be consistently higher than that of a system without one. Second, the reduction in processing time required for the job is closely related to the reduction in power required. Therefore, for battery operated systems, A fixed-point implementation could greatly extend battery life. The following statements summarize the results from the experiment in this section:

1. A competent assembly programmer can beat the assembler, in some cases by a very large margin.

2. If computational performance is critical, then a well-designed fixed-point implementation will usually outperform even a hardware-accelerated floating point implementation.

3. If there is no hardware support for floating point, then floating point performance is extremely poor, and fixed point will always provide the best performance.

4. If battery life is a consideration, then a fixed-point implementation can have an enormous advantage.

Note also from the table that the assembly language version of the fixed-point sine function beats the identical C version by a wide margin. Section 9.8.2 will demonstrate that a good assembly language programmer who is familiar with the floating point hardware can beat the compiler by an even wider performance margin.