Sign in to follow this  
MindWipe

Fixed point math question (16.16)

Recommended Posts

Heya, so I want to know the distance beteen two 16.16 points. I wrote my own sqrt that work great on 16.16 values. My problem is this however: mySqrt( vX * vX + vY * vY ); vX * vX will overflow, and it doesn't help to switch to longs, as the value sent to mySqrt will be larger than what fits in 32bits. So how do I solve this? /MindWipe

Share this post


Link to post
Share on other sites
Do the multiply and add first, using 64bit intermediates, then convert back to 16.16 for the sqrt, or write a 32.32 sqrt if the precision is too important.

Basically:
mySqrt( (int)(((long)vX * (long)vX + (long)vY * (long)vY) & 0x0000FFFFFFFF0000) > 16 )

Also, is the true distance really important here, or just this distance relative to another? In the later case, the sqrt can be avoided altogether by simply comparing the non-sqrt'ed values. In the case that you have one value which is a true distance and another which is not, simply square the true distance and compare that instead.

Share this post


Link to post
Share on other sites
I had a similar problem once. When you multiply two fixed point numbers of the form m.n, then the result becomes a number of 2m.2n and does need twice the space as before. The integer square root will reduce it to m.n again, but you have to be careful where the dot ends up.

I implemented the algorithm found here:
http://en.wikipedia.org/wiki/Shifting_nth-root_algorithm
If B is 2 (binary), then the algorithm simplifies a lot. With every iteration the algorithm will consume 2 bits of the input value and produce one bit of output.

If you use a 32 bit integer to store values with a form of 8.16 and zeros in front, then multiplication of two values will still fit into a 32 bit integer. Applying the iteration of the sqrt as described above for 24 steps will give you the corresponding result.


Another solution I can think of is to scale the values into a range of 0 to 1 and use a 0.n fixed point format. Since all values are smaller than 1 now, multiplication will give no overflow anymore (unlike division :).

Share this post


Link to post
Share on other sites
Hey thanks guys!! That information helped alot! And distance is very important, as it's in a physics engine, unfortunately.

/MindWipe

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this