Not all numbers on a computer can be represented as integers! As a result, we need ways to represent fractions. There are many possible ways of doing this; consider, for example, representing fractions using a numerator and a denominator, as:
typedef struct rational {
int numerator, denominator;
} rational;
Given this, we could define addition, subtraction, multiplication and division
functions. For example, we might define addition as:
rational_add(a,b,c);
rational * a,b,c;
{
a->denominator = b->denominator * c->denominator;
a->numerator = b->numerator * c-denominator
+ c->numerator * b-denominator;
}
This is ugly, but in high level languages that allow operator overloading,
once the definitions are finished, the cumbersome problems with this
number representation can be hidden from view. There is, however, one
problem with this number system, that of reducing rational numbers to their
simplest form; so for example, we would rather see 3/4 instead of 36/48.
Because of this, most work done on computers uses a different approach to representing fractional values, either using fixed point binary numbers or using floating point binary numbers. Of these, floating point is by far the most common approach, but floating point numbers are based on fixed point numbers, so it is best to explain the the latter first.
Fixed point number representation is based on a simple idea. Instead of counting units, so that the least significant digit of the number is the one's place, count some fraction. For example, in the fixed point decimal system we use to describe financial transactions, the least significant digit counts in units of 1/100 of a dollar. So, when I look at my postal receipt for $10.65, I have:
place 10 1 1/ 1/
values /10 /100
_____ _____ _____ _____
| | | | |
| 1 | 0 | 6 | 5 |
|_____|_____|_____|_____|
In printing fixed point numbers on paper, we use a period to indicate where
the 1's place is. We call this a decimal point, but in fact, the period has
nothing to do with the number base and everything to do with telling where
the 1's place is.
Fixed point binary numbers are just as useful as fixed point decimal. For example, we can use the following representation of 2.75:
place 2 1 1/ 1/
values /2 /4
_____ _____ _____ _____
| | | | |
| 1 | 0 | 1 | 1 |
|_____|_____|_____|_____|
In print, we would represent this as 10.11 (binary). Formally, this is
a 4-bit fixed point binary number with 2 places after the point, or in
slightly more compact terminology, a 4-bit fixed point binary number with
a 2-bit fraction.
On the Hawk computer, with its 32 bit word size, we would typically use 32 bit fixed point numbers, and an obvious question comes up: How does the programmer select the number of bits used to represent the fraction? The answer is that this depends on the problem.
Consider a problem in computer aided design, where you are represeing dimensions of the parts of some machine. The precision needed for these dimensions depends on the manufacturing technology! If, for example, your the tools used to measure and cut machine parts can only operate to a precision of 1/100 millimeter, then if we represent these dimensions in millimeters to the nearest 1/128 millimeter. This is probably close enough, but it is tempting to use an 8 bit fraction and round dimensions to the nearest 1/256 millimeter just to be on the safe side. Additional precision is unlikely to be needed.
So, we come up with the following binary number representation for our computer aided design system:
_______ _______ _______ _______ _______ _______v_______ _______
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
24 bit integer part ^ 8 bit fraction
This allows representation of dimensions up to 16 million millimeters
(2 to the 24th) to the nearest 1/256 millimeter (2 to the minus 8th).
There are problems with the above representation. Yes, it does allow representation to greater than the 0.01 millimeter precision required by the application, but it does not allow for cumulative error. Consider the following problem:
A part requires 101 holes drilled in a line. Each hole is to be 1.1 mm from its neighbor and 1 mm diameter.Note that the 0.1 cannot be accurately represented as a binary fraction. The closest fixed point binary representations to 1.1, using an 8 bit fraction are 1.00011010 and 1.00011001, which are about 1.10156 and 1.09766; thus, our error in representing the space between consecutive holes will be either +.00156 or -.00234, both well within the acceptable precision of 0.01 millimeter.
The problem comes up with the specification that there are to be 101 uniformly spaced holes. If these holes are all 1.10156 mm apart, the distance from the first hole to the last will be 110.156 mm, while our specification calls for a distance of 110.00 mm. Here, the error is .156 mm, quite a bit larger than the 0.01 mm precision we are required to keep, and quite likely a sufficient error to cause significant problems.
Short of designing all dimensions in the products of our machine shop to conform to the system of number representation used inside our computer system, there is a solution to our problem! While the specifications call for 101 uniformly spaced holes, we must take into account the inaccuracy in measurement and use alternating spacings of 1.10156 and 1.09766 mm; if we alternate these spacings appropriately, it is easy to keep the error below 1/100 mm.
How do we compute this alternation? There are exact methods, but the easiest is to simply assign extra precision to all of our fractions whenever we are computing extended summations, and then round the result to the specified precision. For example, if we use a 16 bit fraction, we can add up 512 numbers before errors in the least significant bits of the numbers being added could accumulate to creep into 0.01 mm range.
Can we afford to use a 16 bit fraction? To use this fraction, we had to steal 8 bits from the integer part of our originally proposed number representation. How big an integer part do we need? The original problem statement was in terms of a machine shop, and our original proposal allowed for a 24 bit integer part, representing millimeters! Recall that one thousand is roughly 2 to the 10th, and one million is roughly 2 to the 20th. Thus, a 24 bit number allows us to represent values on the order of 16 million. 16 million millimeters is 16 thousand meters or 16 kilometers, far larger than any machine shop!
We have precision to spare, but can we afford to give up 8 bits? Instead of 24 bits, we are proposing to use only 16 bits for the integer part of our dimensions. 16 bits allows a maximum dimension of about 64 thousand millimeters, or 64 meters. This is large enough for a machine shop that builds toasters or locomotives, but it is not enough for a shipyard; many ships are well over 64 meters long!
This brings us full circle! Selecting a number representation requires a clear understanding of the the problem being solved! A number representation that is more than sufficient for the auto industry may not work for shipyards or aerospace applications. Furthermore, selecting a number representation requires an understanding of the impact of any arithmetic to be performed as well as of the precision of individual numbers. insufficient for use in a s
The rules for addition, subtraction, multiplication and division of fixed point binary numbers are the same rules students learn in elementary school for dealing with decimal fractions!
For addition or subtraction, you first align the points, then add. In decimal, to add 3.75, 4.6 and 12.2, we would align the points and add as follows:
3.75
4.6
+ 12.2
--------
20.55
In binary, programming in C, we might do a similar problem as follows:
int a; /* fixed point with a 4 bit fraction */ int b; /* fixed point with an 8 bit fraction */ int c; /* fixed point with a 12 bit fraction */ /* -- some time later in the program -- */ c = (a << 8) + (b << 4) + c; /* shift operatons above are used to align the points */The shift operations shown above (using the << operators) are there to align the points in the binary fractions. The points are not explicitly represented anywhere in the code understood to the compiler, they are there only in the comments and in the progrmmer's mind.
A few languages allow users to declare fixed point numbers with their precision, and the compilers automatically do the appropriate shifting before addition. Among these are IBM's PL/I, defined in the mid 1960's and widely used in the early 1970's, and Ada, defined in the late 1970's and widely used for defence applications today.
The same example, coded in SMAL Hawk assembly code, might be written as:
LOAD R1,A ; get number with 4 bit fraction LOAD R2,B ; get number with 8 bit fraction LOAD R3,C ; get number with 12 bit fraction ADDSL R1,R2,4 ; add R2 to (R1 << 4) ADDSL R1,R3,4 ; add R3 to (R1 << 4) STORE R1,C ; save result ; shifts above are required to align the points!Multiplication is slightly more complex. The rule, multiplying decimal fractions, is that the number of places after the point in the product is the sum of the number of places after the point in the multiplier and in the multiplicand. This is illustrated in the following decimal example:
1 2.7 5 - 2 places after the point
x 2.6 - 1 place after the point
----------
7 6 5 0 +
2 5 5 0 ----
----------
3 3.1 5 0 - 3 places after the point
The same rule applies in binary! Consider the following example in C:
int a; /* fixed point with a 4 bit fraction */ int b; /* fixed point with an 8 bit fraction */ int c; /* fixed point with a 12 bit fraction */ /* -- some time later in the program -- */ c = a * b /* no shift needed */ c = (a * a) << 4 /* product has an 8 bit fraction */ c = (b * b) >> 4 /* product has a 16 bit fraction */The final example above required a right shift to discard the least significant 4 bits of a 16 bit fraction before storing that number in a variable declared to have a 12 bit fractional part. As shown above, this code simply throws away the least significant bits, but it should have rounded.
To round, add 1 to the most significant of the bits to be discarded. For example, to round the final product in the above example, use:
c = ((b * b)+8) >> 4 /* product has a 16 bit fraction */Here, note that 8 is 1000 binary, and we are throwing away 4 bits, so this indeed adds 1 to the product in exactly the right position required by our rounding rule.
As a general rule, to retain the maximal fractional precision, rounding and right shifts to discard bits should be deferred as long as possible. Thus, for example, if a sum of numbers with 8 bit fractions is to be computed, and then stored in a number with a 4 bit fraction, first compute the sum using high precision, then round to the lower precision!
Division follows the same rules for binary fixed point numbers as it does for decimal fixed point numbers: If the divisor has n places after the point and the dividend has m places after the point, the quotient will have m - n places after the point. This follows from the rule that quotient times divisor equals dividend and the rule for computing how many places the product has after the point!