Fixed Point
Fixed point arithmetic is a simple and often [1]good enough method of
computer representation of [2]fractional numbers (i.e. numbers with higher
precision than [3]integers, e.g. 4.03), as opposed to [4]floating point
which is a more complicated way of doing this which in most cases we
consider a worse, [5]bloated alternative. Probably in 99% cases when you
think you need floating point, fixed point will do just fine. Fixed point
arithmetic is not to be [6]confused with fixed point of a function in
mathematics (fixed point of a function f(x) is such x that f(x) = x), a
completely unrelated term.
Fixed point has at least these advantages over floating point:
* It doesn't require a special hardware coprocessor for efficient
execution and so doesn't introduce a [7]dependency. Programs using
floating point will run extremely slowly on systems without float
hardware support as they have to emulate the complex hardware in
software, while fixed point will run just as fast as integer
arithmetic. For this reason fixed point is very often used in
[8]embedded computers.
* It is natural, easier to understand and therefore better predictable,
less tricky, [9]KISS, [10]suckless. (Float's IEEE 754 standard is 58
pages long, the paper What Every Computer Scientist Should Know About
Floating-Point Arithmetic has 48 pages.)
* Is easier to implement and so supported in many more systems. Any
language or format supporting integers also supports fixed point.
* It isn't ugly and in [11]two's complement doesn't waste values (unlike
IEEE 754 with positive and negative zero, denormalized numbers, many
[12]NaNs etc.).
* Some simpler (i.e. better) programming languages such as [13]comun
don't support float at all, while fixed point can be used in any
language that supports integers.
How It Works
Fixed point uses a fixed (hence the name) number of digits (bits in
binary) for the integer part and the rest for the fractional part (whereas
floating point's fractional part varies in size). I.e. we split the binary
representation of the number into two parts (integer and fractional) by
IMAGINING a radix point at some place in the binary representation. That's
basically it. Fixed point therefore spaces numbers [14]uniformly, as
opposed to floating point whose spacing of numbers is non-uniform.
So, we can just use an integer data type as a fixed point data type, there
is no need for libraries or special hardware support. We can also perform
operations such as addition the same way as with integers. For example if
we have a binary integer number represented as 00001001, 9 in decimal, we
may say we'll be considering a radix point after let's say the sixth
place, i.e. we get 000010.01 which we interpret as 2.25 (2^2 + 2^(-2)).
The binary value we store in a variable is the same (as the radix point is
only imagined), we only INTERPRET it differently.
We may look at it this way: we still use integers but we use them to count
smaller fractions than 1. For example in a 3D game where our basic spatial
unit is 1 meter our variables may rather contain the number of centimeters
(however in practice we should use powers of two, so rather 1/128ths of a
meter). In the example in previous paragraph we count 1/4ths (we say our
scaling factor is 1/4), so actually the number represented as 00000100 is
what in floating point we'd write as 1.0 (00000100 is 4 and 4 * 1/4 = 1),
while 00000001 means 0.25.
This has just one consequence: we have to [15]normalize results of
multiplication and division (addition and subtraction work just as with
integers, we can normally use the + and - operators). I.e. when
multiplying, we have to divide the result by the inverse of the fractions
we're counting, i.e. by 4 in our case (1/(1/4) = 4). Similarly when
dividing, we need to MULTIPLY the result by this number. This is because
we are using fractions as our units and when we multiply two numbers in
those units, the units multiply as well, i.e. in our case multiplying two
numbers that count 1/4ths give a result that counts 1/16ths, we need to
divide this by 4 to get the number of 1/4ths back again (this works the
same as e.g. units in physics, multiplying number of meters by number of
meters gives meters squared). For example the following integer
multiplication:
00001000 * 00000010 = 00010000 (8 * 2 = 16)
in our system has to be normalized like this:
(000010.00 * 000000.10) / 4 = 000001.00 (2.0 * 0.5 = 1.0)
SIDE NOTE: in practice you may see division replaced by the shift operator
(instead of /4 you'll see >> 2).
With this normalization we also have to think about how to bracket
expressions to prevent rounding errors and [16]overflows, for example
instead of (x / y) * 4 we may want to write (x * 4) / y; imagine e.g. x
being 00000010 (0.5) and y being 00000100 (1.0), the former would result
in 0 (incorrect, rounding error) while the latter correctly results in
0.5. The bracketing depends on what values you expect to be in the
variables so it can't really be done automatically by a compiler or
library (well, it might probably be somehow handled at [17]runtime, but of
course, that will be slower). There are also ways to prevent overflows
e.g. with clever [18]bit hacks.
The normalization and bracketing are basically the only things you have to
think about, apart from this everything works as with integers. Remember
that this all also works with negative number in [19]two's complement, so
you can use a signed integer type without any extra trouble.
Remember to always use a power of two scaling factor -- this is crucial
for performance. I.e. you want to count 1/2th, 1/4th, 1/8ths etc., but NOT
1/10ths, as might be tempting. Why are power of two good here? Because
computers work in binary and so the normalization operations with powers
of two (division and multiplication by the scaling factor) can easily be
optimized by the compiler to a mere [20]bit shift, an operation much
faster than multiplication or division.
Code Example
For start let's compare basic arithmetic operations in [21]C written with
floating point and the same code written with fixed point. Consider the
floating point code first:
float
a = 21,
b = 3.0 / 4.0,
c = -10.0 / 3.0;
a = a * b; // multiplication
a += c; // addition
a /= b; // division
a -= 10; // subtraction
a /= 3; // division
printf("%f\n",a);
Equivalent code with fixed point may look as follows:
#define UNIT 1024 // our "1.0" value
int
a = 21 * UNIT,
b = (3 * UNIT) / 4, // note the brackets, (3 / 4) * UNIT would give 0
c = (-10 * UNIT) / 3;
a = (a * b) / UNIT; // multiplication, we have to normalize
a += c; // addition, no normalization needed
a = (a * UNIT) / b; // division, normalization needed, note the brackets
a -= 10 * UNIT; // subtraction
a /= 3; // division by a number NOT in UNITs, no normalization needed
printf("%d.%d%d%d\n", // writing a nice printing function is left as an exercise :)
a / UNIT,
((a * 10) / UNIT) % 10,
((a * 100) / UNIT) % 10,
((a * 1000) / UNIT) % 10);
These examples output 2.185185 and 2.184, respectively.
Now consider another example: a simple [22]C program using fixed point
with 10 fractional bits, computing [23]square roots of numbers from 0 to
10.
#include <stdio.h>
typedef int Fixed;
#define UNIT_FRACTIONS 1024 // 10 fractional bits, 2^10 = 1024
#define INT_TO_FIXED(x) ((x) * UNIT_FRACTIONS)
Fixed fixedSqrt(Fixed x)
{
// stupid brute force square root
int previousError = -1;
for (int test = 0; test <= x; ++test)
{
int error = x - (test * test) / UNIT_FRACTIONS;
if (error == 0)
return test;
else if (error < 0)
error *= -1;
if (previousError > 0 && error > previousError)
return test - 1;
previousError = error;
}
return 0;
}
void fixedPrint(Fixed x)
{
printf("%d.%03d",x / UNIT_FRACTIONS,
((x % UNIT_FRACTIONS) * 1000) / UNIT_FRACTIONS);
}
int main(void)
{
for (int i = 0; i <= 10; ++i)
{
printf("%d: ",i);
fixedPrint(fixedSqrt(INT_TO_FIXED(i)));
putchar('\n');
}
return 0;
}
The output is:
0: 0.000
1: 1.000
2: 1.414
3: 1.732
4: 2.000
5: 2.236
6: 2.449
7: 2.645
8: 2.828
9: 3.000
10: 3.162
Links:
1. good_enough.md
2. rational_number.md
3. integer.md
4. float.md
5. bloat.md
6. often_confused.md
7. dependency.md
8. embedded.md
9. kiss.md
10. suckless.md
11. twos_complement.md
12. nan.md
13. comun.md
14. uniformity.md
15. normalization.md
16. overflow.md
17. runtime.md
18. bit_hack.md
19. twos_complement.md
20. bit_shift.md
21. c.md
22. c.md
23. sqrt.md