3
$\begingroup$

I am trying out a few forms of polynomial expression optimization, and I'd like to improve of what I've got, if anyone has anything they know is better.

Implementation 1:

$$x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}$$

To the best of my knowledge, this has 3 add/subtracts, 21 muls, and 3 divs.

Implementation 2:

$$x(1+x^2(\frac{-1}{3!} + x^2(\frac{1}{5!} + x^2(\frac{-1}{7!}))))$$

This appears to have 3 adds/subracts, 13 muls, and 3 divs. This is assuming that $x^2$ is precalculated. (I may have counted wrong here.)

Implementation 3:

$$x(1+\frac{x^2}{3!}(-1 + \frac{x^2}{5*4}(1 - \frac{x^2}{7*6}))))$$

This appears to have 3 adds/subtracts, 6 muls, and 3 divs. Edit: Again, assuming a precalculated $x^2$.

Note: In all my factorial calculations, I have not done the $*1$ final multiply.

Am I doing anything wrong here, or is there any way this implementation can be made more computationally efficient?

$\endgroup$
4
$\begingroup$

Taylor series is not a good way to do this; it takes a lot of terms to get reasonable accuracy.

I answered a similar question on stackoverflow a while ago. Here's the body of the answer:

Here are some good slides on how to do power series approximations (NOT Taylor series though) of trig functions: http://www.research.scea.com/gdc2003/fast-math-functions.html

It's geared towards game programmers, which means accuracy gets sacrificed for performance, but you should be able to add another term or two to the approximations to get some of the accuracy back.

The nice thing about this is that you should also be able to extend it to SIMD easily, so that you could compute the sin or cos of 4 values at one (2 if you're using double precision).

If you really really want to use Taylor series, check out "Fast Polynomial Evaluation" in part two of the linked slides; it provides some examples of Estrin's Method.

$\endgroup$
  • 1
    $\begingroup$ This is very useful, thank you. It also solves the primary issue of finding a optimized way of evaluating said functions. $\endgroup$ – Chronum Oct 30 '15 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.