Fixed point math question (16.16)
Author
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
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.
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.
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 :).
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 :).
Author
Hey thanks guys!! That information helped alot! And distance is very important, as it's in a physics engine, unfortunately.
/MindWipe
/MindWipe
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
