Re: faster impl of atan2 in java...
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