Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve MathUtils.asin(), acos() #6332

Merged
merged 1 commit into from Dec 27, 2020
Merged

Conversation

tommyettinger
Copy link
Member

The average and largest error are significantly better for this version (2-3 orders of magnitude), and it can be slightly faster. For comparison, this implementation uses one Math.sqrt() call (on a float argument and cast to float, which HotSpot optimizes well), whereas the implementation it replaces uses one float division. These seem to have about the same performance cost on modern Intel hardware; it may be different on AMD processors or ARM. In terms of accuracy, there's no comparison; the previous asin() in MathUtils was only usable if the high error near inputs of -1 and 1 wasn't noticeable.

This algorithm was described in a 1955 research study by RAND Corp, "Approximations for Digital Computers." There are other approximations for asin() described, but the first one, on sheet 35, is the fastest. It's also the least precise of the approximations they give, but it's still much more precise than the current one, which is by Dennis Kjaer Christensen.

I did a comparative benchmark for the previous MathUtils (in GDXASinBench), this PR (in ASin35FloatBench, 35 because the approximation was on sheet 35), and Math (MathASinBench). Higher is better; each of these measures ops/second:

 ASin35FloatBench score: 94179176.000000 (94.18M 1836.1%)
 GDXASinBench score    : 91518944.000000 (91.52M 1833.2%)
 MathASinBench score   : 38451616.000000 (38.45M 1746.5%)

The acos() implementation here is slightly faster than asin(), because it can avoid adding or subtracting PI or HALF_PI in one of its branches. I benchmarked all of these on a 10th-gen i7 hexacore laptop processor, and performance is likely to vary somewhat on much older PCs because of how thoroughly Math.sqrt() gets optimized on recent CPUs.

I also compared the absolute average error, relative average error, and largest single absolute error for both approximations. These were computed for 2048 equally-spaced floats from -1 (inclusive) to 1 (exclusive).

 ASin35: absolute error 0.000028447, relative error -0.000000033, max error 0.000067592
 GDX   : absolute error 0.007147891, relative error -0.000007316, max error 0.023241536
 Math  : no error, because we're comparing relative to Math.asin()

If anyone has any questions, just ask; the previous approximations for asin() and acos() weren't tested enough by me when I had suggested them a while ago. I knew they were fast, but I didn't know there were faster approximations that had better accuracy.

The average and largest error are significantly better for this version (2-3 orders of magnitude), and it can be slightly faster.
@NathanSweet NathanSweet merged commit 7933720 into libgdx:master Dec 27, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants