gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > fast inv square

#80035 - Ant6n - Tue Apr 18, 2006 4:55 am

stumbled across this thing,
pretty cool
- it uses newton-rhapson with 1 iteration (!!), and a black magic number with evil bithacking to get first approx to get 3 sigfigs
http://www.codemaestro.com/reviews/review00000105.html

#80092 - tepples - Tue Apr 18, 2006 7:42 pm

The "evil bit hacking" involves floating-point numbers, but the Newton's method that follows may still apply to GBA and Nintendo DS programming.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#80094 - sajiimori - Tue Apr 18, 2006 7:50 pm

Seems like the magic number should apply, too, though encoded in fixed-point format instead of floating point.
Code:
int magicInt = 0x5f3759df;
float magicFloat = *(float*)&magicInt;

// Overflow?  Use long long maybe.
int magicFx32 = magicFloat * 4096;

print("The magic fixed-point value is %x\n", magicFx32);

#80098 - keldon - Tue Apr 18, 2006 7:55 pm

Interesting.

#80128 - kusma - Wed Apr 19, 2006 1:19 am

sajiimori wrote:
Seems like the magic number should apply, too, though encoded in fixed-point format instead of floating point.


not at all. the trick depends on a exponent/mantissa solution.

...and seriously, if you're serious about graphics optimizations and haven't heard about this trick before, well... you're way behind. ;)

it's a neat hack that has never been really demystified (although some guy wrote a paper attempting to do so, but failed miserably), but as pointed out, not really relevant on gba. besides, you can do quite nice lut-based rsq-routines in fixed point anyway. and again, your square roots are rarely your main bottleneck.

#80130 - gladius - Wed Apr 19, 2006 1:45 am

kusma: Are you talking about http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf? I read that one a while back and it seemed pretty solid to me. It was written by someone who knows his numerical methods pretty well.

Dave Eberly also took a crack at explaining the "magic number", and he's a pretty trustworthy source as well :). His paper is here http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf.

#80153 - kusma - Wed Apr 19, 2006 10:03 am

heh, it seems my memory didn't serve me well. both papers seems to do a good job explaining it, tho i still feel some details are left out (like the dangers of carry propagating from the mantissa to the exponent). but then again this might just be me being too stupid to see what is supposed to be obvious.

#80168 - tepples - Wed Apr 19, 2006 1:57 pm

kusma wrote:
(like the dangers of carry propagating from the mantissa to the exponent)

This was the "more difficult case" from the first paper.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#80262 - Ant6n - Thu Apr 20, 2006 6:36 pm

kusma wrote:
sajiimori wrote:
Seems like the magic number should apply, too, though encoded in fixed-point format instead of floating point.

...and seriously, if you're serious about graphics optimizations and haven't heard about this trick before, well... you're way behind. ;)
...


gee, I guess if I was serious about that I wouldnt post here, now would I?

And if I came across that and didnt know about it and thought it was interesting, then chances are somebody else might find it interesting, too. It is interesting to see if people find ways to implenent certain problems that seem completely odd. Maybe it could be an inspiration to find something like that yourself.

And yes, square roots, especially inverse square roots, can be a bottle neck - they are not if everything you do is plain 2d ... but I guess you know that.

anyhoo

#80394 - kusma - Fri Apr 21, 2006 11:06 pm

Ant6n wrote:

gee, I guess if I was serious about that I wouldnt post here, now would I?

And if I came across that and didnt know about it and thought it was interesting, then chances are somebody else might find it interesting, too. It is interesting to see if people find ways to implenent certain problems that seem completely odd. Maybe it could be an inspiration to find something like that yourself.

Sure, whatever.

Ant6n wrote:

And yes, square roots, especially inverse square roots, can be a bottle neck - they are not if everything you do is plain 2d ... but I guess you know that.

If your 3d engine is frame-limited due to square roots, you are doing something very very wrong. first of all, fixed point (as well as floating point, but that is another story on this forum) RSQs can be implemented quite bloody fast using a clz and a look-up table (quite similar to the division trick I've discussed on this forum before). But hey, a good gba-level 3d engine should probably not contain any square nor inverse square roots anyway.