1
$\begingroup$

First, sorry if this post is off-topic. I consider it too analytic for stack overflow.

In Numerical Analysis subject I must explain which one is better (has less error). The recursive implementation seems to be better with the inputs I have used, but I don't know the reason.

Can someone explain to me which one is better and why? Having in mind round-off error and loss of significance using doubles.

Iterative implementation:

$$\cos{x} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ ... \ + (-1)^n\frac{x^{2n}}{(2n)!}$$

Recursive implementation:

$$y_{n+1} = (-1)^n$$ $$y_{k} = \frac{y_{k+1}x^2}{(2k)(2k-1)} + (-1)^{k-1}, \ \text{for} \ k=n,\ n-1,\ n-2,\ ... \ 1$$

$\endgroup$
  • 1
    $\begingroup$ Do you need arbitrary precision or not? If you want a fast approximation with an ahead-of-time fixed precision polynomial approximations (sometimes augmented with little tricks) are often really fast and really precise. Usually series like these are not used for actual computation unless you need thousands of digits as they often converge quite slow and are expensive to compute. $\endgroup$ – orlp May 2 '17 at 21:14
1
$\begingroup$

The main problem with the iterative approach is that the terms of the series get smaller and smaller with increasing index, so if you sum terms from 1 up, you eventually end up adding values of very small magnitude to accumulated sums of much larger magnitude. When done using floating-point arithmetic, that's pretty much the same as simply discarding terms after some point. The recursive approach sums the same terms, but in reverse order, so all the small terms get a chance to accumulate into larger sums before the larger terms get added; this lets the smaller terms actually contribute to the final sum.

I suspect that the way the recursive approach builds up the larger factorials in small steps also helps produce more accurate sums.

$\endgroup$

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.