Why does this iterative C++ algorithm approximate cosine?

[pokeka]

Hi, this is my first post. Hope I'm not breaking any rules. Anyway, I was messing arround programming the other day, and I accedently came up with an algorithm that will approximate the cosine of a number with a great deal of precisision. Here's the code:

double cosine(double n){
double a=1;
double da=0;
double p=1000;//Bigger numbers will give you a better value for cos(n)
for(double i=0;i<=n;i+=pow(p,-1)){
da+=-a/pow(p,2);
a+=da;}
return a;}

It's kinda hard to put this into words, and I imagine a lot of people here know a little bit of c++, so, for now, I won't try to explain what it does. I can try though, if you want. So, yeah, if anyone could tell me why this works, that would rock.

 

[StatusX]

OK, I think I was able to derive this correctly. I really hope this isn't homework, as I put a lot of time into this for you to just be cheating off me. I'll see if I can explain this concisely, but it'll be tough. First, we'll write out the recursion relation explicitly:

$$da_n=da_{n-1}-\frac{1}{p^2} a_{n-1}$$

$$a_n = a_{n-1} + da_{n}$$

Where a₀=1 and da₀=0. Next we define:

$$\alpha \equiv -\frac{1}{p^2}$$

And we find:

$$da_n=\alpha(a_0+a_1+ ... +a_{n-1})$$

And similarly:

$$\begin{align*} a_n &= da_0+... + da_{n-1}\\<br /> &=1+ \alpha \left( (a_0) + (a_0+a_1) + ... + (a_0+...+a_{n-1})\right) \\<br /> &=1+ \alpha \sum_{k=0}^{n-1} (n-k) a_k \end{align*}$$

Which eliminates the need for the da_n. Now, you can see by computing a few terms that the a_n will have the form:

$$a_n=\sum_{j=0}^n c_{nj} \alpha^j$$

For some constants c_nj. Plugging this into the above equation:

$$\begin{align*} \sum_{j=0}^n c_{nj} \alpha^j &=1+ \alpha \sum_{k=0}^{n-1} (n-k) \sum_{j=0}^k c_{kj} \alpha^j \\<br /> &=1+\sum_{j=0}^{n-1} \alpha^{j+1}\sum_{k=j}^{n-1} (n-k)c_{kj} \end{align*}$$

Equating like powers of $\alpha$ gives a recursion relation for c_nj:

$$c_{nj}=\sum_{k=j-1}^{n-1} (n-k)c_{k j-1}$$

With initial conditions c_n0=1. Now, it turns out these coefficients are (2j)th order polynomials in n. We will be taking the limit as $\alpha$ goes to zero later on, and n will go to p=1/$\sqrt{\alpha}$, so we're only interested in the highest power of n. Thus, we will use the approximation:

$$c_{nj} \approx b_j n^{2j}$$

Also, the following approximation holds to first order (as you'll see, we actually approximate a series that doesn't start at 1 by this formula, but the limit justitifies this):

$$\sum_{k=1}^{n-1} k^q \approx \frac{1}{q+1} n^{q+1}$$

So that:

$$\begin{align*}b_j n^{2j} &= \sum_{k=j-1}^{n-1} (n-k) b_{j-1} k^{2j-2} \\<br /> &=n\sum_{k=j-1}^{n-1}b_{j-1} k^{2j-2}-\sum_{k=j-1}^{n-1} b_{j-1} k^{2j-1} \\<br /> &\approx \frac{1}{2j-1} n^{2j} b_{j-1}- \frac{1}{2j} n^{2j}b_{j-1} \\<br /> &=\frac{1}{(2j)(2j-1)} n^{2j} b_{j-1} \end{align*}$$

And so:

$$b_{j} = \frac{1}{(2j)(2j-1)} b_{j-1}$$

And together with b₀=1, we have our first non-recursive results, even though they're only approximate:

$$b_j= \frac{1}{(2j)!}$$

$$c_{nj} \approx \frac{n^{2j}}{(2j)!}$$

$$a_n \approx \sum_{j=0}^n \frac{n^{2j}}{(2j)!} \alpha^j$$

We are interested in a_px (I'm using x here where the OP used n) This is given by (putting back in p):

$$\begin{align*}a_{px} &\approx \sum_{j=0}^{px} \frac{{(px)}^{2j}}{(2j)!} \frac{(-1)^j}{p^{2j}}\\<br /> &=\sum_{j=0}^{px}(-1)^j \frac{x^{2j}}{(2j)!}\end{align*}$$

Which, in the limit p>>1/x (x>0) gives:

$$a_{px} &\approx \sum_{j=0}^{\infty} (-1)^j \frac{x^{2j}}{(2j)!}=cos(x)$$

The taylor series for cos(x). Anyone know an easier way?

 

[StatusX]

Oh, you're welcome pokeka. Not a problem. Your thank you made it all worth while...

 

[Sartak]

Oh, you're welcome pokeka. Not a problem. Your thank you made it all worth while...

If it's any consolation, I am certainly impressed. :)

 

[StatusX]

If it's any consolation, I am certainly impressed. :)

Thanks. Sorry I'm bitter, but I did put a bit of work into that.