Faster math algorithm sacrificing accuracy

Question

Hi, I am developing a game that calls so many math functions for physics and rendering. "Fast inverse sqrt" used in Quake3 is known to be faster than sqrt() and its background is beautiful.

Do you know any other algorithm that is faster than usual one with acceptable accuracy loss?

Answer 1

These algorithms are called "approximation algorithms" in literature. The standard book with plenty of examples is Approximation Algorithms by Vijay V. Vazirani.

The case of sin x ~~ x is a special case of something slightly more general: Look at the Taylor series (or Fourier series in the case of periodic functions) of your function and compute only the first few terms.

Another (somewhat brutal) technique is to randomly assemble a few points of your function and then run a linear regression against it. That way, you can get a good polynomial describing your function, too :).

Answer 2

for small x: sin(x) ~= x is one that is often used in physics

Answer 3

Anything probabilistic is usually like this. Running a simulation 10 times will be faster, but yield less accurate results than running a simulation 1000 times.

Answer 4

Niko has some good suggestions to which I'd add the old fashion look up table.

I've used a look up table for circular functions (sin/cos/tan) successfully many times in high performance real time systesm. The sqrt() is harder this way, but if your input range is restricted (to say screen pixels) it's hard to beat for speed, and you can tune the space/accuracy trade off exactly. You can also use the look up for a common range, and then have a fallout to a framework sqrt() function for the rare case.

Paul

Answer 5

Any continuous function (which includes most common math operations) can be well approximated over a bounded interval by a polynomial. This, together with relatively simple identities that common math functions usually satisfy (like addition laws) and table lookups, provides the basis of the standard techniques to construct fast approximation algorithms (and also the basis of high accuracy methods like those used in the system math library).

Taylor series are usually a poor choice, however; Chebyshev or Minimax polynomials have much better error characteristics for most computational uses. The standard technique for fitting minimax polynomials is to use Remes' Algorithm, which is implemented in a lot of commercial math software, or you can roll your own implementation with a day's work if you know what you're doing.

For the record, the "fast inverse square root" should be avoided on modern processors, as it is substantially faster to use a floating-point reciprocal square root estimate instruction (rsqrtss/rsqrtps on SSE, vrsqrte on NEON, vrsqrtefp on AltiVec). Even the (non-approximate) hardware square root is quite fast on current Intel processors.

Answer 6

From the Doom source code, for approximate distance between two 2D points without having to use sqrt() or trigonometric functions:

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy )
{
    dx = abs(dx);
    dy = abs(dy);
    if (dx < dy)
        return dx+dy-(dx>>1);
    else
        return dx+dy-(dy>>1);
}

Note that x >> 1 is the same as x / 2 but slightly faster - good modern compilers do this automatically nowadays but back then they weren't so great.