Darwinbots Forum
Code center => Darwinbots Program Source Code => Topic started by: Greven on October 02, 2005, 06:33:58 AM
-
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.
-
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.
-
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... ;) )
-
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.
-
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...
-
I was afraid of something like that... When I was researching how to do DLLs, I found a disclaimer at the bottom of an obscure page that said something to the effect that often times its faster to use VB code because interfacing with other languages can be slow.
Anyway, I guess I have to go back and figure out how to make the speed increase real... lol.
Notably, often times when you're taking the sqr, you then divide something by it. So for it to be a good test, you should add a third case where you have some large number divided by the sqr, or multiplied by the invsqrt.
-
I dont think it would make difference really.
-
I don't either, not a significant one anyway...
-
I have read millions of articles about optimization in VB, and calls to DLL, is on the negative side, it slows down it very very much.
-
Well, that's one idea out the window :P
Problem is this fast function uses bit manipulations that aren't accessible in VB. I may just go back to the old Newton iterative method, which is still fast but uses divisions...
-
Just so it doesn't seem I was randomly pulling out source code to play with:
The article on inverse square root (http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf).
-
looks fun :P
-
I think I have a function figured out that's native VB for square root function.
I'm going to see if it's faster or no.
-
Nope, the best I can do is a function that's less accurate and just as fast.
Really goes to show the amount of overhead involved in visual basic. Or the speed of the VB sqr function :rolleyes: