Jump to content
  • Advertisement
Sign in to follow this  
MindWipe

Fixed point math question (16.16)

This topic is 3851 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!