Fixed Integer Math?

[Ironside]

Dan do you know any good links to info about fixed integer math? Or maby just a sentance or two on the basic concept. I'm working on a software engine for the Ipaq and i've wrapped up the float datatype into a class so it will be easy to change it's implementation. I just can't seem to find any good info on fixed integer math..

[Ironside]

Found some stuff. <br>http://www.cstone.net/~kyoung/fix1FAQ.html<br>http://www.cstone.net/~kyoung/fix2FAQ.html

[Dan East]

Well, I'm still looking myself.  I also have looked through the docs you referred to above.  The problem is that most info has assembly source, which is of course x86.  <br>http://gameprogrammer.com/4-fixed.html has CPP source.  That example uses 18.14 precision, but I'm using 16.16 for Pocket Quake.  The main problem I've encountered is how to convert a negative int to fixed point.  Shifting left works, but not for negative ints.  Anybody have any idea on that one?<br><br>Dan East<br>

[Dan East]

Ok, I was wrong about the negative ints.  Shifting does indeed work to convert to and from negative values.  I was encountering a different problem: overflow/underflow.<br><br>Dan East

[Mark Rejhon]

Ouch!<br><br>I hope that problem is easy to resolve, since you've modified nearly 3000 lines of code, probably under the assumption of using 16.16 fixed point values.  I hope that doesn't mean big trouble for the upcoming PocketQuake release!<br><br>Maybe you can define higher precision "intermediate" 24.8 and 8.24 types, for those special cases, with functions to convert between fixed point formats.

[Dan East]

Well, where I enountered it is a spot where ID Software just chose an arbitrary max and min (999999, -99999), which exceeded the fixed point range.  I don't know why they chose a min with 5 digits and a max with 6.  :)  I may have to sacrifice precision to gain range, or vice versa as you mention.<br><br>Dan East

[killzat - Mark]

The underflow/overflow has been known to cause problems with even some modern engines. Not always directly related but worth saying.

[CARPEDIEM]

Well, i've been having trouble with float numbers myself, im currently developing a GAPI Benchmark utility and i also thought for like an hour about fixed point integers, and i finally realized it wasn't necesary. Plus it probably take several lines of coding and i would have ended up with a slow data type like doubles.<br>My problem was making a tree like fractal work, but without using floating point math. My first approach was, like i said, fixed point math. But then i realized that i just needed it for trigonometric functions, and if i ever needed other operations i would have been able to solve them in the same manner. Which im about to expain. in the next post

[CARPEDIEM]

First of all, if you need trigonometric functions, for games, then BY NO MEANS you need to use fixed point math, or even a taylor polinomial.<br><br>What you have to do for the sin function por example, is generate an int array of 720 components, and in each of them, place the corresponding value for sin(i - 360). Because  <br>sin[0] will mean sin(-360).<br>But of course, these values vary between -1 and 1, and if you cast the double to an int, you'll always get a 1 or a 0.<br>The solution is to multiply sin(i)* 10000, so that you don't loose the valuable info.<br><br>And whenever you want to use this sin table, you can use it normally on any expression, and divide everything for 10000. And voila, you get what you want at a cheap cpu price.<br><br>Using integer math i get like 200-300% speed increase. Pretty damn neat, i can't belive you get 10 fps on pocket quake even using floating point math. When you leave this damned data type, i assure you, quake will FLY.<br><br>So, Basically you can use these multiplications for 10000 to simulate a decimal point in any operation, you loose range of course, but there are larger data types than just ints so who cares, they sure as hell are faster than integers.<br><br>I hope i was of some help.<br>

[CARPEDIEM]

I ment, faster than floating point data types.<br>

[Roland Persson]

Actually, multiplying and dividing by some constant (10000 in your case). Is essentialy fixed point arithmetic but misses one key point that can make things go even faster.<br><br>Integer multiply and divide should also be avoided if possible, a multiplication costs about 30-50 cycles on modern CPUs and division usually costs about 20% more. This should be compared to addition and other simple instructions that take perhaps only 1 or 2 cycles.<br><br>Shifts also cost just 1 or 2 cycles and this is a key thing to take advantage of. If you would chose a constant that is a power of 2 instead of 10000 you could replace all divides and multiplies by that constant with shift operations.<br>If you would chose 2^14 (16384) as your constant your multiplications turn into shifting left by 14 and your divisions into shifting right by 14.<br><br>How much faster things will go because of this depends ofcourse upon how much time is occupied by the current constant multiplies and divides.<br>That time however, will essentialy become no time if you switch to shifts.<br><br>/Roland

[Ironside]

Actually I got some fixed point code off THE PHANTOM (jakko bikker). He uses a 20.12 format that seems to work quite well.<br><br>He's actually got an ipaq 3d engine that loads a 2k plus poly 3ds mesh that's texturemapped and it runs well.<br><br>I'll post the code tonight when I get home. But after Some comparisions between fixed point and floating point, this is what i found<br>Ipaq:<br>    Fixed point is 9x faster then floating<br><br>Athalon 800 desktop PC:<br>    Fixed point is 2x SLOWER then floating point

[Ironside]

Also dan, i think the 20.12 format would work well with the specifications you descibed (999999 , -99999)<br><br>This is because 20 bits can completly contain 999999 (6 nines) <br>and 99999 (5 nines) fits nicely inside 17 bits wich leaves an extra 2 bits to hold the negative flag if you need it.

[Daniel J. MacDonald]

#define FPP 12<br>#define FP_ONE (1<<FPP)<br>#define FPMUL(x,y) ((((x>>2))*((y)>>2))>>(FPP-4))<br>#define FPDIV(x,y) (((x)<<(FPP-2))/((y)>>2))<br>#define FP(x) ((int)((x)*FP_ONE+0.5f))<br>#define IFP(x) ((x)<<FPP)<br><br>the fixed point math code

[Sparky009]

Argh! bitshifting! I'm blind, I'm blind!<br>...