Computers store all data as a sequence of bits.

When we wish to perform numerical computations on a computer, we must decide how to represent our numbers as sequences of bits for the computer to manipulate.

At a very fundamental level, computers interpret numbers directly as integers. In decimal, the sequence of digits \(528\) represents eight 1’s, two 10’s, and five 100’s. We can do the same for binary numbers: \(1101\) represents one 1, zero 2’s, one 4, and one 8.

Fractions

However, what if we want to represent numbers with fractional parts, such as \(0.5\) and \(1.25\)?

A simple way to represent fractional numbers, which I will discuss in this article, is to treat them as integers, but with the decimal point moved some number of places. For example, in decimal we could store \(0.5\) as \(050\), and \(1.25\) as \(125\). We then interpret these numbers in our calculations as if there was a decimal point before the first two digits. This method is called fixed-point representation (because the decimal point is in a fixed position!)

More generally, what we have done here is decide on a common representation factor that we multiply into our numbers to store them. In this case we chose the factor \(F = 100\). To represent a number \(x = 1.25\), we store \(xF = 1.25 \times 100 = 125\).

In practice we often choose some \(F\) which is a power of 2, so that we move the, uh, decimal point, in binary. (Binary point?)

Precision and error

Now, let’s consider what happens when we go to represent \(x = 2.468\). We multiply by our factor to obtain \(xF = 2.468 \times 100 = 246.8\). However, we have a problem: we can’t store this number in a computer as it’s not an integer. Therefore, we’ll have to round it, to \(247\).

In this case, there is error in our representation; we tried to represent \(2.468\) but what we got was a representation of \(2.47\). Essentially, we can only represent numbers to a certain precision, which describes the smallest difference we can measure between two numbers. We can represent differences of up to \(1\) in \(xF\) (because it has to be an integer), so our precision for \(x\) is \(1/F\). The error caused by rounding due to precision is called round-off error. We will explore more sources of error later.

Addition

Now we need to work out how to add, multiply, and do other computation with fixed-point, so we can actually use it!

Let’s work out how to add \(x\) and \(y\). They are represented as \(xF\) and \(yF\). (We will assume these are exact.) We need to get \((x+y)F\), the representation of \(x+y\). This is easy; we can use normal integer addition:

The final step is determining if there’s any error in our computation. In this case, there isn’t, because integer addition is exact. Here’s some code; fixpt is our defined type for fixed-point numbers:

fixpt fp_add(fixpt x, fixpt y) {
    return x + y;
}

Multiplication

Now, how do we multiply \(x\) and \(y\)? We need to get \(xyF\) from \(xF\) and \(yF\).

Great! Now, is there any error?

Unfortunately there is here, because integer division is not exact. When we divide two numbers with integer division, we get a result which has been rounded down to the nearest integer; this means we have an error somewhere between \(0\) and \(-1\). In another words, when we integer-divide \(xyF^2\) by \(F\), instead of getting \(xyF\), we actually get

where double-slash represents integer division.

Another way of writing this is by setting \(\epsilon = \delta/F\). Then we can say that our actual result is

In other words, the actual result of our multiplication has an error of at most \(-1/F\).

fixpt fp_mul(fixpt x, fixpt y) {
    return x * y / FACTOR;  // integer division rounds down!
}

The good news is that we can essentially eliminate this error by using a division routine which rounds to the nearest integer, instead of always rounding down. With this, we have \(-1/2 < \delta \leq 1/2\) after the division, and so our final error \(\epsilon\) is such that \(-1/2F < \epsilon \leq 1/2F\).

fixpt fp_mul(fixpt x, fixpt y) {
    return (x * y + FACTOR / 2) / FACTOR;  // more accurate
}

Why does this “essentially eliminate the error?” It’s still not zero!

Let’s consider: what is the significance of the quantity of the value \(1/2F\)? We established earlier that the precision of a fixed-point scheme with factor \(F\) is \(1/F\). In other words, when we want to represent a number, we have to round it to the nearest multiple of \(1/F\). And the very furthest we can be from such a multiple is half-way between two of them… i.e. at a distance of \(1/2F\)!

What this means is that, if the final result of our computation is within \(1/2F\) of the correct answer, it is no less accurate than the round-off error from just directly inputting the correct answer!

Getting the accuracy within half of the precision is the ultimate goal when designing a numerical computation. Any improvement to that value will be unmeasurable. However, it’s important to realise that there is still error here.

Conclusion

I hope this article gave you a reasonable understanding of these fundamentals of fixed-point schemes, number representations, and precision.

Finally, it’s worth noting that in almost all programming languages, fractional numbers are represented with floating point as it is more widely suitable. But fixed point is sometimes used where specific control of precision is required e.g. accounting, or on small microcontrollers without fast floating point hardware.