speed: integer vs. floating point

[NickJohnson]

I'm writing a simple physics engine, mostly as a programming exercise. I was wondering what the kind of speed differences are between operations on floating point numbers and on integers on modern processors. Mostly this applies to x86 for me, but both speed and consistency are relevant for other architectures.

I'm trying to decide whether to use floats or signed 32 bit integers like fixed point numbers (8 bits past radix). ~80% of the operations will be addition or negation, ~15% will be multiplication, and the rest will be sin(), cos(), and atan() trig functions, which can be roughly approximated with little consequence. It probably won't make a huge difference, but either one will be fine in terms of precision, so the speed is the only factor, afaik.

I couldn't find much information on this through searching, and I didn't want to base my opinion on just my laptop, which has a pentium 3. Thanks!

[pcmattman]

If you're working with physics you probably want as much precision as you can get. The performance penalty is minimal, but jumpy physics due to low precision isn't worth trying to make things "super fast".

[Firestryke31]

It mostly depends on the hardware available. Even if the platform has a FPU, that doesn't mean that it will be faster than just using ints.

I know that on the GBA (and the DS IIRC), there's no FPU, so you were more or less stuck with fixed point. sin() and friends were approximated with LUTs and, if necessary, interpolation. Heck, there was even one part of the hardware that expected 8.8 fixed numbers for 2D screen transformations. I would suggest looking there for something to get ideas from.

If you optimize it correctly, then it shouldn't be too much slower than floats on a platform with a good FPU.

However, floats are almost always better for precision. If you're just looking for experience writing an optimized library, I say go fixed. If you're planing on using this physics library for something where imprecision is noticeable, like a game, I would say go with floats and find something else to optimize, like rendering. There are some pretty funky tricks for that if you're working in 3D.

[NickJohnson]

I don't have a specific purpose for this engine yet, but I guess I'm probably going to make some sort of game for it eventually. But I don't see how a 24.8 or 20.12 fixed point number is going to be inaccurate even for games. It seems to me that games would need the least precision, because the results don't really matter as long as they're physics-ish, unlike scientific physics simulations.

[Firestryke31]

It depends on the scale. If the precision is wrong for the scale, you'll get jumpy results, or be wasting potential magnitude. If objects moving at 0.125 millimeters per frame are relatively common then you'll need the precision to represent that, while minimizing the waste of being unable to move more than 536.870911 kilometers per frame. Of course, if that's overkill then you might want to go ahead and sacrifice some magnitude for precision.

Edit: Those numbers are assuming unsigned fixed 29.3 numbers. Half the kilometer number if you want to use signed.

[AndrewAPrice]

I don't have a specific purpose for this engine yet, but I guess I'm probably going to make some sort of game for it eventually. But I don't see how a 24.8 or 20.12 fixed point number is going to be inaccurate even for games. It seems to me that games would need the least precision, because the results don't really matter as long as they're physics-ish, unlike scientific physics simulations.

Perhaps, but it would depend on the game. I worked on one small project that consisted of rendering a galaxy procedurally, and even for a planet the size of the earth (which is smallish in comparison to, say, Jupiter), when using the centre of the planet as the frame of reference (that is, 0,0,0) the surface was noticeably inaccuracy. Especially on high peaks where the camera would 'pop'. After trial and error, it was found the best way was to switch to doubles (the other methods would have overcomplicated the problem without a significant performance boost). When zoomed out from a planet, the frame of reference was changed so that 0,0,0 represented the sun and 1 unit = 100 km. At the galaxy level 1 unit = 1 light year. Changing frames of reference wasn't only good mathematically, but provided a point at which you could performance rendering optimisations (such as baking the surrounding star system into a skybox when entering the planet's frame).

That is somewhat a dramatic example, but even when dealing with 16-bit floats you can get vertices on your mesh popping on an average sized map once they've been transformed by the world/view matrix, and a 16-bit Z buffer is near impossible to use.

The question also comes down to if you will be doing a lot of floating/fixed point conversions when communicating to other libraries, including rendering.

If you're not rendering or interacting with the simulation in real time, then you could go against the question asked in your original post and go for the most accurate method. I'm not an expert in this field, but it would be interesting to make a numerical class which doesn't store the number internally, but rather as an optimised tree to create that number, only returning the numeric value when required.

[skyking]

Generally there's should be no big difference as long as the word width is the same (for example single precision vs 32-bit ints). If you don't have an FPU (like arm) you might be better of by using ints, otherwise for some processors (like PPC) you'd be better of using floats. Fix point also has the advantage of not having variable absolute precision depending on the magnitude of the number.

[NickJohnson]

I've decided to switch to floats - the benchmarks are almost the same, and there might even be a speed advantage later due to trig functions, and the multiplication is not obfuscated. I wrapped the type used for measurements (float right now) in a typedef, so I can change it more easily later. I don't see much of a difference in precision though.

[Owen]

If you're objective is performance, then I have one thing to say to you:

Compiler optimizers suck.

Most of the time they do a good enough job, but for math intensive jobs like Physics, you're going to have to give them a helping hand, with things like the SSE intrinsics.

When people say compilers can optimize better than humans, they're only partially right: Compilers only do large scale optimizations better; Smaller scale ones, such as inner loops, can only be at present achieved manually. None of the compilers in use today (And this includes ICC!) are any good at vectorizing.

[fara7at]

I've done some experiments with integer arithmetic vs. floating point arithmetic when I was toying with the idea of representing points and doing transformations in fixed point. (This was mainly because the results were to be used as indices into a 3D volume, and in CPU time, the compiler-generated x86 processor state change to trunc mode to do an integer cast is like watching continental drift.

[Brendan]

Hi,

However, floats are almost always better for precision.

Floating point numbers have higher "best case" precision, while fixed point integers have higher "worst case" precision.

Imagine you need to store a number that ranges from -127.999999999999999999999 to 127.999999999999999999999. Using a "7.24" fixed point integer (and proper rounding), you end up with +/- 0.0000000298023223876953125 precision.

Using a 32-bit floating point number, the significand (which determines your worst case precision) is only 25-bits (not 32-bits), so the precision is worse. For example, the closest number to 127.999999999999999999999 is 1111111.111111111111111111b (or 127.999996185) and the next closest number is 1111111.111111111111111110b (or 127.999992371); and you end up with +/- 0.0000019073486328125 precision (which is 64 times worse than the precision you'd get from a fixed point integer).

For floating point, the closer a number gets to zero the more precise it becomes; and because of this for "best case" precision floating point wins by a massive margin.

For something like physics modelling in games you want higher "worst case" precision (and not higher "best case" precision). If someone fires a rocket along the edge of the game map, then it should be just as precise as someone firing a rocket near the centre of the game map.

The only way to improve "worst case" precision is to increase the number of bits you're using - e.g. use a larger integer, or a floating point number with a larger significand. A 64-bit floating point number (a "double") will be better than a 32-bit fixed point number, but a 64-bit fixed point number will be better than a 64-bit floating point number.


Cheers,

Brendan

[Firestryke31]

Well, at least I tried to be generically helpful with that "almost." I really need to learn how floats work. I've never needed to do anything weird with them, and I never thought about accuracy at different scales, so I know nothing of their internal format.

[ot]Blarg, I was trying to figure out how to work ice cream and soda in there, but it never materialized.[/ot]

[Owen]

Of course, that is assuming that your playfields don't exceed the boundaries of your fixed point integers.

Most physics engines use floats because, firstly, 25 bits of precision is more than enough except at extreme values, games use different scales, and they run faster on processors with an FPU (I.E. those running a physics engine).