9 Replies Latest reply on Aug 3, 2007 2:25 PM by Rothrock

    Fast Inverse Square Root

      I expect no replies to this thread - because there are no answers, but I want to raise awareness of a faculty of other languages that is missing in Flash that would really help 3D and games to be built in Flash.

      Below is an optimisation of the Quake 3 inverse square root hack. What does it do? Well in games and 3D we use a lot of vector math and that involves calculating normals. To calculate a normal you divide a vector's parameters by it's length, the length you obtain by pythagoras theorem. But of course division is slow - if only there was a way we could get 1.0/Math.sqrt so we could just multiply the vector and speed it up.

      Which is what the code below does in Java / Processing. It runs at the same speed as Math.sqrt, but for not having to divide, that's still a massive speed increase.

      But we can't do this in Flash because there isn't a way to convert a Number/float into its integer-bits representation. Please could everyone whinge at Adobe about this and give us access to a very powerful tool. Even the guys working on Papervision are having trouble with this issue.
        • 1. Re: Fast Inverse Square Root
          Rothrock Level 5
          That is really quite interesting. Can you explain what the "f" in 0.5f*x and x*(1.5f-xhalf*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 Adobe Community Professional & MVP
            the f converts those numbers to floating point numbers.
            • 3. Re: Fast Inverse Square Root
              Rothrock Level 5
              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 Adobe Community Professional & MVP
                the technique depends upon converting between the float and integer 32-bit 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 Level 5
                  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 Adobe Community Professional & MVP
                    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 look-up 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^^(E-e/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 look-up, at most, two inverse roots, perform one multiplication and one decimal shift:

                    inverseRt(x) = 10^^(-e) * inverseRt(10) *inverseRt(m), if E-e/2 = 1 and

                    inverseRt(x) = 10^^(-e) * inverseRt(m), if E-e/2 = 0.
                    • 7. Re: Fast Inverse Square Root
                      Rothrock Level 5
                      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 Adobe Community Professional & MVP
                        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 Level 5
                          Reminds me of the days before we had (good) trig functions.