How to determine the feasibility of using fixed-point numbers on a given (game) project?

Question

I have considered posting this question on GameDev since my case relates to a game project, but I figured this would be more suited for a broader programming SE. Please let me know if this question would be better posted there after all.

From my understanding - and please correct me if I'm wrong -, game development for mobile (which is my case) can benefit considerably from employing fixed point calculations, since that would assure more consistency betweens platforms and would be an increase in performance in cases where the device isn't well-equiped to deal with floating point appropriately.

But fixed-point does have limitations, most notably with overflows. So my question is, assuming we have determined that fixed-point is the best alternative given the target platforms, how to determine if a given project's requirements allow for their use.

To make things clearer, I'd like to share a bit of code I'm having trouble with:

CIwVec2 calculateBezier(float t, CIwVec2 p0, CIwVec2 p1, CIwVec2 p2) {
    float u = 1 - t;

    CIwVec2 p = IW_FIXED(u * u) * p0;   // (1 - t)²P0
    p += IW_FIXED(2 * u * t) * p1;      // 2(1 - t)tP1
    p += IW_FIXED(t * t) * p2;          // t²P2

    return p;
}

In this project I'm using Marmalade SDK, which uses C++ and comes with their own implementation of fixed-point numbers (they have both 16 and 32-bit, I'm using 32-bit as of now), and a Vector class (CIwVec2) which uses that implementation for position and calculations (including scalar multiplication, which is shown in the code above). Oh, and IW_FIXED is just a macro to convert floats to fixed-point.

When I try to run the above code, I get a Multiply overflow error. Debug values as follows:

t = 0
u = 1 (which converts to 4096 in int32 fixed-point with IW_FIXED)
p0.x = 1638400 (400.0f with IW_FIXED_TO_FLOAT)
p0.y = 409600 (100.0f with IW_FIXED_TO_FLOAT)

To be perfectly honest, I don't have a complete understanding on fixed-point numbers. I understand the idea, but fixed point operations aren't entirely clear to me (I must have ditched most math classes relating to base 2, shame on me). But I'm completely boggled by the fact that something as simple as 1.0f * 400.0f would cause an overflow in fixed-point.

So, while I thought I wouldn't have a problem supporting fixed-point in my project, it appears it might not be the case. The game is a top-down car game, which won't have huge tracks or anything, but they'll have to be at least as big as the device's screen (or better yet, its resolution), and since we're aiming for tablets as well, having trouble with something like 1.0f * 400.0f means fixed-point is out of the question.

Am I correct with this assumption? And, for future projects and for other people with similar problems, how can we assess the viability of fixed-point numbers in a project? Also how to decide between 16-bit and 32-bit would be a great bonus :)

(Sorry for the long post and thanks for your time!)

Update:

So, so sum up a bit of the responses so far. The ideal scenario would be to implement your fixed-point numbers in such a way as to have the necessary range for your needs (Mooing Duck's anwer). Also, for operations with 32bit numbers, the safest thing to do is to calculate using 64bit (timday's answer and Max's comment). By the way, Marmalade does have some "safe fixed multiplication" functions, but it's not the case with the scalar multiplication operator overload for CIwVec2 (which uses IW_FIXED_MUL underneath, which does not mupliply safely).

And lastly, more in regards to my particular scenario, it appears that as of Marmalade 6.1, just using floats would probably be the best solution.

Edit: Although Max's answer really solved my problem, it was mostly because it was something specific to Marmalade. Because of that, I have selected Mooing Duck's answer as the selected answer since I feel is the one which would help out more people in general.

Answer 1

Fixed point can be viewed as storing the top half of a fraction, and the bottom half in your case is 4096. So 1.0f is equal to 4096/4096, and it's stored in memory as 4096. I won't go into the details of fractional multiplication because I don't remember them, but the important part is when multiplying A/D * B/D to get a result C/D, then C is A*B/D.

So: where you have 1.0f * 400.0f, the computer sees this as 4096 * 1638400 / 4096. A little algebra shows this should result in 1638400 (400.0f), but if the fractional point library isn't smart enough for that, it ends up with a temporary value of 6710886400 before it does the division, which is too big for an int.

Since your floating points have a denominator of 4096, your "floats" are accurate to the closest 0.00024, and have a range of -524288.999f to 524287.999f (ish). Is there a way in your compiler to decrease the accuracy of the "floats" to get more range? Otherwise you're hosed.

EDIT

Max confirms that the 4096 is part of Marmalade and cannot be changed. In that case, I see few options:
(1) Don't use fixed point.
(2) Try to keep all floating point numbers between -128 and 128.
(3) Use a special function for multiplying a scalar and a CIwVec2 that uses IW_FIXED_MUL underneath. Preferably, wrap the float in a special class and overload the operator* to call IW_FIXED_MUL. Don't provide an implicit conversion to float, otherwise you'll never find all the errors.

Answer 2

What you're seeing and the 32-bit intermediates it implies (see Mooing Duck's answer) seems like a severe weakness to me.

I have used fixed point libs successfully in the past (on x86 in the 386/486 era) and they all used a 64bit intermediate for multiplies before the correcting shift (In fact I seem to remember Intel provided a very nice 32x32-to-64 bit multiply instruction which was just perfect for this). The higher intermediate precision bought you quite lot of freedom over data ranges; I'd really hate to work with something as restricted as this Marmalade lib seems to be, but can see why they might have had to do it for portability reasons.

Answer 3

It does not make sense to use fixed point in mobile development today when you use Marmalade 6.1 Marmalade 6.1 it was released in September.

There are few android phones without FPU but most phones has FPU, GPU with GLES 1.0 and GLES 2.0 We target GLES 2.0 devices with Marmalade now.

The reason Marmalade has IW_FIXED is that they have their own graphics layer called IwGX.

Before September 2012 (Marmalade 6.1). IwGX was not supporting float point. That is why developers were forced to use fixed numbers even when they targeted recent GLES 2.0 devices.

There is no benefit to use fixed numbers with marmalade today.

--

Anyway if you still wish to multiple with fixed point there is IW_FIXED_MUL function

ADDED: Code in example is correct.