Thursday, January 1, 2009

Fixed Point

What do you do if you need numbers after the decimal point? Use floats? What is wrong with that is that floats are slow. Really slow. How can we fix that? Fixed point math. The idea behind fixed point math is that we pretend that there is a decimal point. In order to have enough bits, we use a long. That gives us 32 bits. 8 bit precision after the decimal point, 16 bit before. The reason this works is because, if you do all of you math without the decimal point, and then add the decimal point, you get the same result. But, because all we need is precision that is eventually going to be mapped to an integer matrix such as the screen, we don't need to add the decimal point at all.
Okay, you might say, but how can we convert a integer to a fixed point? Easy. Just shift foward eight bits, like this:
    fixed_var = (long) int_var << 8 
The next problem is converting floats. Because floats are in IEEE format, shifting will thrash them. To get around this, we must multiply by 256, which is the eighth power of two.
   fixed_var = (long) float_var * 256;
We can convert back to an integer like this:
   int_var = (long) fixed_var >> 8;
Addition and subtraction work are basically the same with fixed point numbers are they do with integer or floats. Multiplication is harder, however. The problem is, the computer sees each number as having a addition eight zeros on it. So if you are multiply 100 * 100, you actually get 100*100*256. Once you figure out the problem, however it's no problem. You simply shift back eight zeros. If you have a series of multiplications, you can shift after all the calculation is done.
   fixed3 = (long) (fixed1 * fixed2) >> 8;
Next problem: Division. The problem with division is basically the same as the problem with multiplication: An unwanted factor crops up in the calculation. The way we fix this is to shift the dividend left eight times.
   fixed3 = (long) (fixed1 * fixed2) >> 8; 
Okay, why don't we create a small library of functions to deal with fixed point? The reason: functions are too slow. The same goes to C++ classes. What we can do is create a bunch of macros, which will work just fine. You can download this file here.
typedef long fixed;   // Our new fixed point type.
#define itofx(x) ((x) <<>> 8)   // Fixed point to integer
#define fxtof(x) ((float) (x) / 256) // Fixed point to float
#define fxtod(x) ((double)(x) / 256) // Fixed point to double
#define Mulfx(x,y) (((y) * (x)) >> 8) // Multiply a fixed by a fixed
#define Divfx(x,y) ((y <<>>8,100*(unsigned long)((x)&0x00ff)>>8) // Print fixed point.
#define NDPrintfx(x) printf("%ld", x >> 8) // Print fixed point without a decimal point.

No comments:

Post a Comment