Re: faster impl of atan2 in java...
Eric Sosman wrote:
Daniel Pitts wrote:
Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...
----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.
Long, long ago I learned of this system as "binary angular
measure," with the smallest angular increment called "one bam."
In my application, one bam was 2*pi/65536.
The Vector class stores its value as a pair of floating (double
precision) values.
>
After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase :-)
But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.
----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.
OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.
On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.
The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.
A few random thoughts:
A few comparisons of signs and magnitudes of the vector's
X and Y components would get you to the correct octant, and a
binary search for "closest" could choose among the thirty-two
possible angles in five steps.
As above, but use an interpolation search instead of a
binary search. At a guess this might lose in complication
what it gains in step count, but maybe a hybrid strategy would
help: interpolate to find the first probe position, then go
step-by-step from there on the assumption that you won't need
to take very many steps.
What would happen if you stored rho and theta in your
vectors along with (or even instead of) X and Y? Whether this
is practical probably depends on where these vectors come from
and what gets done to/with them along the way.
--
Eric Sosman
esosman@acm-dot-org.invalid
First off, thanks for the replies (everyone).
The vector is often a difference of two position vectors. as in, I'm
trying to find the angle between two points in my grid.
Would a binary search really be faster? I don't know how its
implemented internally, but storing tangent in my precomputed Angle
objects would be trivial.
A little more context might help.
Basically, I have an "Arena" with many "Robots", each robot has (at
least) a location "Vector" and a "Scanner". The Scanner has a heading
"Angle", and an arcWidth (int, but same scale as Angle, and probably
should be an angle, but thats a later refactoring).
When the robots program requests a scan, the scanner (asks the arena)
for the closest robot that is within the scan arc. The scan arc has
the same location as the scanning robot, and the heading of the
Scanner.
So, the approach I'm taking is to go through every robot in the arena,
check to see if it in the scan arc (this is where the atan2 comes in),
and if it is closer than any previous match.
For an arena with 30 robots, each scanning a few times a second, that
translates into a lot of scans.
Although, I'm wondering if there isn't some algorithm that will help me
reduce the number of robots I need to select through, something like
quadrant reduction, or maybe first ordering the robots from closest to
farthest, and then finding the first robot in that list which is withen
the scan arc. I would think that Math.atan2 is slower that Math.hypot.
Am I wrong?
Thanks again for the suggestions, I appreciate it. If I can minimize
the amount of times atan2 is called, then my original question is
pointless, however, I will look into some sort of binary search.
- Daniel.