Code center > Darwinbots Program Source Code

The FastInvSqrt function!

(1/3) > >>

Greven:
Although faster than normal squareroot functions (maybe haven't tested it)

But The FastInvSqrt has an error rate around 0.1 - 3 (and up) %!The error rate is based on how high x is is so FastInvSqrt(9)^-1 gives 0.3 %, while FastInvSqrt(2500)^-1 gives 8 %!!!!

I dont know if this matters difference from the real values matters.

Numsgil:
I copied the function from an article someone wrote about it.  You see, square root is one of those oft used functions that take up big processing power.

Someone (probably smarter than me :P) figured out that you can approximate the inverse square root using a nifty amount of approximation and some numerical techniques (which aren't totally above my head, but are still quite complicated).

Said function is what the Quake 2 Engine uses, I believe.  If it's good enough for Quake 2, it's good enough for me.

The awesome thing is that it only uses multiplication and addition, which is fast.  Want to find the actual square root?  Well, just take x * (invsrt(x))!  Wow, is that cool.

The current code may not run noticable faster (could even be slower) because I had to undo alot of optimizations I'd made over the months to test things.  But the sqrt function should be orders of magnitudes faster.

Greven:
Okay I believe you, I just wanted to point it out. I will try some testing  the Sqrt vs. InvSqrt, just to check the difference. Not in DB, just in general. But it is up to you, Numsgil, to decide if an error rate of 8 % can be accepted!? You are the one with insight in the formula etc., and therefore you are the one who should know if it makes a big impact on the simulation.

Now Quake 2 and DB are two entirely different computer programs, and in DB it could make a lot of difference if a algorithme is very dependent on the Sqrt, and thus making large differences in the sim. Just like the butterfly-effect, just a tiny whiny change can in the long run, have HUGE effects on the outcome. (I consider you intelligent enough to know what the butterfly-effect is... ;) )

Numsgil:
I think in numerical analysis you use the relative error instead of the absolute error.  It's been a while since I took those classes.  So take your error / (real value) to get relative error.

sqrt is used primarily for things like tie forces and vision.  Everything seems to work fine in that regard.

I believe the speed increase is worth the decreased accuracy.  If we need to, we can uncomment a line in the function (the c++ module) that iterates it one more time, for increased accuracy, but in most cases the two or three iterations it's already doing is sufficient.

Greven:
I am back with some test of the normal Sqr function and the FastInvSqr function...

What have I discovered!!!!????

Function have on a run of 10,000,000 calls the following stats:

The Sqr function (normal VB 6): 300 - 400 (compiled)
The FastInvSqrt function (Nums new): 800 and up!? (compiled)

The FastInvSqrt is NOT faster than normal, and I think because of the DLL calls it makes.

Check the file I have attached...

Navigation

[0] Message Index

[#] Next page