Robo Home | Changes | Preferences | AllPages

In the interest of reducing the number of SlowBots out there, does anyone have algorithms to approximate square roots, sines, etc.? Ideally these would be continuous functions rather than simply using the nearest cached value. For that matter, are approximations really faster? I got worried when I saw that the default implementation of Math.sqrt() is to call StrictMath?.sqrt() but it might be fast enough already :-p

/SquareRoot /Sine? /Cosine? /Tangent? /AngleFromX1Y1toX2Y2?

--David Alves

Edit Conflict: "Are you sure an approx algo will be much faster than the built in ones? I think it's best to avoid them completly if you can, for example it's often possible to leave things as squares, hence the Point2D.DistanceSq?() method, and similar. -- Tango"

Seems we had the same thought... -- Tango

Next question is if fast as ever math functions will help those SlowBots. -- PEZ

It would if they have a slow function in an inner loop and we can find a significantly faster one. :-p --David Alves

most of my PM guns use squareroots in the inner loop to compare the positions. I also thought about to remove this and just use the square of the distance. The bad thing is I couldn't recognize a difference at all. -- rozu

Doesn't surprise me. I think it's the loops in themselves that go for too long and too deep. I have no idea if it must be so though since I have no clue what's going on. =) -- PEZ

The normal way to make trig functions work fast is to load the values into an Array at start-time and use values from that. Gives slightly less precision but it ought to be much faster (though Java arrays are kind of slow. :-\). -- Jamougha

Is it any faster to multiply a number with the * operator in java by a power of 10, a power of 2, or does it not matter (i'm talking about double * number, so the bit shift doesnt apply)? -- Scoob

I wrote somewhere that you could use lookup tables (the loading values into the array thing), though it's probably a waste of time in java, you aren't losing most of your robot's speed in trig, you're losing it in long search algorithms and other brute force stuff (or so I would assume, and PM speeds tend to prove me right here) and even moreso to overhead on everything you do. Comparing the square of the distance is a very valid technique that yields exactly the same results (as long as you square everything) and is commonly used, but again, you're not losing most of your speed here. Compared to the huge overheads in java (it is basically interpreted, after all) everything else is probably going to pale, and adding code for a complex approximation algorithm is probably just going to hurt you because it's so much more stuff to interpret. Better to optimize the stuff that has to be written out in your code like your searching, smoothing, matching and whatnot loops. Make your PM work O(x) instead of O(x^582367082465) like some of them seem to, and you'll see more performance enhancement then you ever will from fiddling with your math. -- Kuuran

I so totally agree. Most of this goes for any programming language. But especially for Java, where there are quite a few well payed and competent library designers at work to try to optimize speed for common tasks. If you implement your own stuff, and by some incredible magic manage to get it faster than the standard library alternative, chanses are that next version of Java will do it faster than your own stuff. And think about all those bugs you can have in your own implementation, that are ironed out in the standard libraries. Next thing is that code whre the prgrammer has tried to optimize for speed tend to be much harder to read and maintain than code optimzed for readability and maintainability. Chanses are high that you can see an overall better / faster design in a readable piece of code that you would never see in a speed-optimized piece. The general rule I think is to be very reluctant to optimize for speed. And only do it when yo really have a speed problem and you are dead sure about where the problem lives. Even then you should probably think twice before going ahead. Use profiling tools to analyze your code. Granted, with some PMs out there we really see a speed problem. I managed to speed up the LeachPMC pattern matcher by a factor of 80 or so by using binary searching and being picky about when to run the matcher. -- PEZ

Is anyone using a performance profiler with Eclipse effectively with their robots? I am a little unclear how it would even work, since you usually use such a tool by running your code as an application / unit test. -- The Martinator

yep ...

-- FnH

Robo Home | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited March 8, 2006 19:08 EST by dD576B58F.access.telenet.be (diff)