What's the best way to do fixed-point math?

Question

I need to speed up a program for the Nintendo DS which doesn't have an FPU, so I need to change floating-point math (which is emulated and slow) to fixed-point.

How I started was I changed floats to ints and whenever I needed to convert them, I used x>>8 to convert the fixed-point variable x to the actual number and x<<8 to convert to fixed-point. Soon I found out it was impossible to keep track of what needed to be converted and I also realized it would be difficult to change the precision of the numbers (8 in this case.)

My question is, how should I make this easier and still fast? Should I make a FixedPoint class, or just a FixedPoint8 typedef or struct with some functions/macros to convert them, or something else? Should I put something in the variable name to show it's fixed-point?

Answer 1

Whichever way you decide to go (I'd lean toward a typedef and some CPP macros for converting), you will need to be careful to convert back and forth with some discipline.

You might find that you never need to convert back and forth. Just imagine everything in the whole system is x256.

Answer 2

Chaning fixed point representations is commonly called 'scaling'.

If you can do this with a class with no performance penalty, then that's the way to go. Depends heavily on the compiler and how it inlines. If not, then you need a more traditional C-style approach. The oo approach will give you compiler-enforced type safety which the traditional implementation only approximates.

@cibyr: has a good oo implementation. Now for the more traditional one.

To keep track of which variables are scale, you need to use a consistent convention. Make a notation at the end of each variable name to indicate whether the value is scaled or not, and write macros SCALE() and UNSCALE() that expand to x>>8 and x<<8.

#define SCALE(x) (x>>8)
#define UNSCALE(x) (x<<8)

xPositionUnscaled = UNSCALE( 10);
xPositionScaled = SCALE( xPositionUnscaled);

It may seem like extra work to use so much notation, but notice how you can tell at a glance that any line is correct without looking at other lines. For example:

xPositionScaled = SCALE( xPositionScaled);

is obviously wrong, by inspection.

This is a variation of the Apps Hungarian idea that Joel mentions in this post.

Answer 3

The original version of "Tricks of the Game Programming Gurus" has an entire chapter on implementing fixed-point math

Answer 4

In modern C++ implementations, there will be no performance penalty for using simple and lean abstractions, such as concrete classes. Fixed-point computation is precisely the place where using a properly engineered class will save you from lots of bugs.

Therefore, you should write a FixedPoint8 class. Test and debug it thoroughly. If you have to convince yourself of its performance as compared to using plain integers, measure it.

It will save you from many a trouble by moving the complexity of fixed-point calculation to a single place.

If you like, you can further increase the utility of your class by making it a template and replacing the old FixedPoint8 with, say, typedef FixedPoint<short, 8> FixedPoint8; But on your target architecture this is not probably necessary, so avoid the complexity of templates at first.

There is probably a good fixed point class somewhere in the internet - I'd start looking from the Boost libraries.

Answer 5

template <int precision = 8> class FixedPoint {
private:
    int val_;
public:
    inline FixedPoint(int val) : val_ (val << precision) {};
    inline operator int() { return val_ >> precision; }
    // Other operators...
};

Answer 6

I wouldn't use floating point at all on a CPU without special hardware for handling it. My advice is to treat ALL numbers as integers scaled to a specific factor. For example, all monetary values are in cents as integers rather than dollars as floats. For example, 0.72 is represented as the integer 72.

Addition and subtraction are then a very simple integer operation such as (0.72 + 1 becomes 72 + 100 becomes 172 becomes 1.72).

Multiplication is slightly more complex as it needs an integer multiply followed by a scale back such as (0.72 * 2 becomes 72 * 200 becomes 14400 becomes 144 (scaleback) becomes 1.44).

That may require special functions for performing more complex math (sine, cosine, etc) but even those can be sped up by using lookup tables. Example: since you're using fixed-2 representation, there's only 100 values in the range (0.0,1] (0-99) and sin/cos repeat outside this range so you only need a 100-integer lookup table.

Cheers, Pax.

Answer 7

Does your floating point code actually make use of the decimal point? If so:

First you have to read Randy Yates's paper on Intro to Fixed Point Math: http://www.digitalsignallabs.com/fp.pdf

Then you need to do "profiling" on your floating point code to figure out the appropriate range of fixed-point values required at "critical" points in your code, e.g. U(5,3) = 5 bits to the left, 3 bits to the right, unsigned.

At this point, you can apply the arithmetic rules in the paper mentioned above; the rules specify how to interpret the bits which result from arithmetic operations. You can write macros or functions to perform the operations.

It's handy to keep the floating point version around, in order to compare the floating point vs fixed point results.

Answer 8

You can try my fixed point class from here: http://www.codef00.com/code/Fixed.h

It is designed to be a near drop in replacement for floats/doubles and has a choose-able precision. It does make use of boost to add all the necessary math operator overloads, so you will need that as well (I believe for this it is just a header dependency, not a library dependency).

BTW, common usage could be something like this:

typedef Fixed<16, 16> fixed;
fixed f;

The only real rule is that the number have to add up to a native size of your system such as 8, 16, 32, 64.

Answer 9

When I first encountered fixed point numbers I found this article very helpful, and it does suggest one way of representing fixed point values.

http://www.embedded.com/columns/15201575?_requestid=65598

I didn't wind up using his union representation for fixed point numbers though. I mostly have experience with fixed point in C, so I haven't had the option to use a class either. For the most part though, I think that defining your number of fraction bits in a macro and using descriptive variable names makes this fairly easy to work with. Also, I've found that it is best to have macros or functions for multiplication and especially division, or you quickly get unreadable code.

For example, with 24.8 values:

 #include "stdio.h"

/* Declarations for fixed point stuff */

typedef int int_fixed;

#define FRACT_BITS 8
#define FIXED_POINT_ONE (1 << FRACT_BITS)
#define MAKE_INT_FIXED(x) ((x) << FRACT_BITS)
#define MAKE_FLOAT_FIXED(x) ((int_fixed)((x) * FIXED_POINT_ONE))
#define MAKE_FIXED_INT(x) ((x) >> FRACT_BITS)
#define MAKE_FIXED_FLOAT(x) (((float)(x)) / FIXED_POINT_ONE)

#define FIXED_MULT(x, y) ((x)*(y) >> FRACT_BITS)
#define FIXED_DIV(x, y) (((x)<<FRACT_BITS) / (y))

/* tests */
int main()
{
    int_fixed fixed_x = MAKE_FLOAT_FIXED( 4.5f );
    int_fixed fixed_y = MAKE_INT_FIXED( 2 );

    int_fixed fixed_result = FIXED_MULT( fixed_x, fixed_y );
    printf( "%.1f\n", MAKE_FIXED_FLOAT( fixed_result ) );

    fixed_result = FIXED_DIV( fixed_result, fixed_y );
    printf( "%.1f\n", MAKE_FIXED_FLOAT( fixed_result ) );

    return 0;
}

Which writes out

9.0
4.5

Note that there are all kinds of integer overflow issues with those macros, I just wanted to keep the macros simple. This is just a quick and dirty example of how I've done this in C. In C++ you could make something a lot cleaner using operator overloading. Actually, you could easily make that C code a lot prettier too...

I guess this is a long-winded way of saying: I think it's OK to use a typedef and macro approach. So long as you're clear about what variables contain fixed point values it isn't too hard to maintain, but it probably won't be as pretty as a C++ class.

If I was in your position, I would try to get some profiling numbers to show where the bottlenecks are. If there are relatively few of them then go with a typedef and macros. If you decide that you need a global replacement of all floats with fixed-point math though, then you'll probably be better off with a class.