This content has been marked as final.
Show 9 replies

1. Re: Fast Inverse Square Root
Rothrock Aug 2, 2007 8:49 AM (in response to Robotacid)That is really quite interesting. Can you explain what the "f" in 0.5f*x and x*(1.5fxhalf*x*x) is? I'm not familiar with C so I don't know where that is coming from. 
2. Re: Fast Inverse Square Root
kglad Aug 2, 2007 9:51 AM (in response to Robotacid)the f converts those numbers to floating point numbers. 
3. Re: Fast Inverse Square Root
Rothrock Aug 2, 2007 9:59 AM (in response to Robotacid)Aha, that is what I was coming to, but I wasn't sure. So kglad what do you think of this algorithm. It really is pretty slick. Is there no way to convert it to things that work in Flash? 
4. Re: Fast Inverse Square Root
kglad Aug 2, 2007 11:44 AM (in response to Robotacid)the technique depends upon converting between the float and integer 32bit representation of the number. that is fast in many languages, but not native in actionscript.
and any coding done in actionscript to allow those conversions is going to be too slow to be useful.
so no, there's no way to use that method.
however, i don't see any problem doing just as well (with accuracy) using twice the computation.
i just don't know what good that is because actionscript isn't that fast with arithmetic operations. so, i don't think even a direct implementation of that code would be a big help despite the op's feeling otherwise. 
5. Re: Fast Inverse Square Root
Rothrock Aug 2, 2007 1:41 PM (in response to Robotacid)I guess you have to make lemonade with the lemons you're given. :)
I the point of my question is that yeah this trick makes use of a particular way that numbers are represented by certain languages on certain processors. So is there some comparable trick that maybe could be used with Flash to speed up some calculations. My brain just doesn't go that way – I pretty much always come up with the brute force solution and can't see anything else. But you on the other hand…
It is just an interesting trick and I wonder how many more tricks I'm missing. 
6. Re: Fast Inverse Square Root
kglad Aug 2, 2007 4:41 PM (in response to Robotacid)that's just an implementation of newton's method for finding the zeros of a differentiable function. for a given x whose inverse sq rt you want to find, the function is:
f(y) = 1/(y*y)  x;
1. you can find the positive zero of f using newton's method.
2. you only need to consider values of x between 1 and 10 because you can rewrite x = 10^^E * m, where 1<=m<10.
3. the inverseRt(x) = 10^^(E/2) * inverseRt(m)
4. you don't have to divide E by 2. you can use bitwise shift to the right by 1.
5. you don't have to multiply 10^^(E/2) by inverseRt(m): you can use a decimal shift of inverseRt(m);
6. your left to find the positive zero of f(y) = 1/(y*y)  m, 1<=m<10.
and at this point i realized what, i believe, is a much faster way to find inverse roots: use a lookup table.
you only need a table of inverse roots for numbers m, 1<m<=10.
for a given x = 10^^E*m = 10^^(e/2) *10^^(Ee/2)*m, where e is the largest even integer less than or equal to E (if E is positive, e is the greatest even integer less than or equal to E, if E is negative), you need to lookup, at most, two inverse roots, perform one multiplication and one decimal shift:
inverseRt(x) = 10^^(e) * inverseRt(10) *inverseRt(m), if Ee/2 = 1 and
inverseRt(x) = 10^^(e) * inverseRt(m), if Ee/2 = 0. 
7. Re: Fast Inverse Square Root
Rothrock Aug 2, 2007 8:00 PM (in response to Robotacid)See. That would have never occurred to me. I will have to work on that a bit this weekend to see what I can learn. Thank you for all you share and give. 
8. Re: Fast Inverse Square Root
kglad Aug 2, 2007 10:14 PM (in response to Robotacid)you're welcome.
i just wonder why this isn't used in 3d gaming if speed's that important. this should be much faster and more accurate than the method cited by the op. 
9. Re: Fast Inverse Square Root
Rothrock Aug 3, 2007 2:25 PM (in response to Robotacid)Reminds me of the days before we had (good) trig functions.