Square root comparison
BlitzMax Forums/BlitzMax Programming/Square root comparison
| ||
Not sure why anybody would care about this. In my particular game I need to take square roots that calculate exactly the same on every computer, and I don't know if Floats are safe for this. I tried using Mike's Arbitrary Precision Math Library but it's very slow, so I discovered an integer-based square root approximation which is much faster. (The results do not need to be 100% accurate, just identical on all machines) Any other suggestions welcome.Strict Import bah.mapm Function integer_square_root:Int(a) 'based on http://www.lbebooks.com/downloads/exportal/Verilog_NEXYS_Example24.pdf Local square = 1, delta = 3 While square <= a square = square + delta delta = delta + 2 Wend Return delta/2 - 1 End Function Const tests = 1000 Local time time = MilliSecs() For Local i = 0 Until tests Sqr(i) Next Print "Sqr took " + String(MilliSecs() - time) + " milliseconds." time = MilliSecs() For Local i = 0 Until tests integer_square_root(i) Next Print "integer_square_root took " + String(MilliSecs() - time) + " milliseconds." time = MilliSecs() For Local i = 0 Until tests New TMAPM.Create(i).Sqrt(8) Next Print "TMAPM took " + String(MilliSecs() - time) + " milliseconds." Sqr took 0 milliseconds. integer_square_root took 4 milliseconds. TMAPM took 61 milliseconds. Edit: That was in debug mode. In release mode: Sqr took 0 milliseconds. integer_square_root took 0 milliseconds. TMAPM took 33 milliseconds. I also realised it wasn't entirely fair as TMAPM was operating at 8 decimal places compared to integer at 0! However changing this only shaved off a few milliseconds - it's still very slow by comparison. |
| ||
| Depending on what numbers you are taking the square roots for, you may be able to also use look up tables. It would be even faster if you are taking square roots of a limited set of numbers, like just 1 to 1000 whole numbers. Calculate them ahead of time to 3 decimal places or something and save them in an array. |
| ||
| I have a look up table for arctan that will blow your mind. (Coming soon) |
| ||
| Just plain Int( Sqr(n) ) should be fine. This is double precision so there is far more accuracy than you really need. |
| ||
| Int(Sqr(1))=1 Int(Sqr(2))=1 Int(Sqr(3))=1 I don't think Int(Sqr(n)) will do it?!?! |
| ||
| It's exactly what he's doing now, just a lot faster. |
| ||
| what if a number is 4.99999 on one computer and 5.00001 on another? |
| ||
| Both would have integer root 2. If one was 3.999999 and the other was 4.000001, *then* you'd have a problem. |
| ||
You could also round the result. Decide what precision you need and round to it. Need 3 decimal places? Then something like this should workSquareRoot:Float = (Int(Sqr(Number)*1000+.5)/1000.0 |
| ||
| Still doesn't quite get round the boundary problem Czar Flavius is talking about. |
| ||
| The proposed work around integer_square_root:Int(a) is working with integers, both input and output. Sqr( integer ) can't be that close to an integer unless it is exactly an integer. It won't be 4.99999 or 5.00001 for example. Sqr(25) is exactly 5.0 while Sqr(24) and Sqr(26) are nowhere near 5. |
| ||
| Ok i'm not worried about the square root so much as for trigonometry. Its a multiplayer game so calculations need to be exact on all computers. I have made look up tables for sin cos and tan but atan2 is proving to be a nightmare. How can i calculate it so that it's the exact same on every computer? One decimal place is sufficient percision. It doesn't matter if the results aren't 100% accurate so long as they are identical on all computers. |
| ||
| Czar: Remember than for speed reasons you can always compare the absolute values. To say, to compare 2 distances for instances, you can avoid the SQR, just compare the quadratic value and use SQR only when you need the exact magnitude |
| ||
| Ok here is the full problem. A turret needs to find a target in range (distance and sqrt), calculate the angle it needs to face taking into account movement of the unit too (atan2). I have this working with both floats and mapm. I'm concerned about floats being the same in every computer (am i worrying about nothing?) and mapm is SLOOOOW if you have more than a few dozen things going on. |
| ||
| if distance < max, then distance*distance < max*max. You don't need to do the square root. For atan2, you could pick an arbitrarily big radius and compute an atan2 lookup table for all integer co-ordinates on that circle. |
| ||
| You are trying to solve some multi-player networking issues... The solution to this sort of problem is to not let the turret make that decision on all of the computers. Pick one machine that will actually be the brains of the turret, either a master server, or on the machine of the player who created it. Let that machine be the only one that controls the brains of the turret. Then when the turret picks a target and fires, just tell all of the other players what the turret has decided to do. Never let multiple machines try to predict the same output. It will always fail. This goes for everything, firing, whether a bullet hits, collisions, etc. Only let one machine check to see if a certain bullet hit, and if that machine decides there is a hit, then tell the other machines. |
| ||
| taskmaster, that's a good idea but it means the game won't run smooth laggy connections. User input is scheduled for a few game frames ahead of the current time, so if there is a sudden lag spike it might not even be perceivable if it's below a few frames' time! letting a computer be the turret's brains would negate this trick and make game performance too dependant on connectivity. I appreciate the advice and i've experienced first hand how annoying sync issues can be but i actually have it working - just very slow with mapm. my game's network design is based on the implementation of age of empires. Warpy could you give more info about how to make that lookup table? |
| ||
| I don't think that your benchmark has realistic results: Basically you are comparing 1000 function calls against 1000 object creation + 1000 method calls. For Local i = 0 Until tests New TMAPM.Create(i).Sqrt(8) Next to get a reliable result you should only compare the direct calls :) Local instance:T... = new T... For Local i = 0 Until tests instance.Sqrt(8) Next don't know the exact type names, therefor the T... |
| ||
| Good point! That saves about a third of the time. Still not enough though :( |
| ||
Should be faster: Herons Method or Babylonian MethodFunction integer_square_root:Int(a:Int) If a=0 Return 0 Local _a:Int = a Local _n:Int = a Local treshold:Int = 2 _n = (_a + a/_a) / 2 While _n <> _a And treshold > 0 _a = _n _n = (_a + a/_a) / 2 If Abs(_n - _a) = 1 Then treshold:-1 'Print "n="+ _n +" a=" + _a Wend If _n < _a Then _a = _n Return _a EndFunction http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method Speed for 1000000 tests (all three functions deliver the same results) Sqr took 156 milliseconds. integer_square_root took 31815 milliseconds. integer_square_root2 took 9461 milliseconds. integer_square_root3 took 872 milliseconds. sqr = bmax sqr integer_square_root = from post 1 integer_square_root2 = enhanced from post 1 (doubling the values instead of incrementing until it is higher than a, then counting down integer_square_root3 = herons method from this post |
| ||
| Thanks!! |
   |