
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!

Why does this work?

  1. Jan 25, 2006 #1
    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)){
    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.
  2. jcsd
  3. Jan 25, 2006 #2


    User Avatar
    Homework Helper

    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:

    [tex]da_n=da_{n-1}-\frac{1}{p^2} a_{n-1}[/tex]

    [tex]a_n = a_{n-1} + da_{n}[/tex]

    Where a0=1 and da0=0. Next we define:

    [tex]\alpha \equiv -\frac{1}{p^2}[/tex]

    And we find:

    [tex]da_n=\alpha(a_0+a_1+ ... +a_{n-1}) [/tex]

    And similarly:

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

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

    [tex]a_n=\sum_{j=0}^n c_{nj} \alpha^j[/tex]

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

    [tex]\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 \\
    &=1+\sum_{j=0}^{n-1} \alpha^{j+1}\sum_{k=j}^{n-1} (n-k)c_{kj} \end{align*}[/tex]

    Equating like powers of [itex]\alpha[/itex] gives a recursion relation for cnj:

    [tex]c_{nj}=\sum_{k=j-1}^{n-1} (n-k)c_{k j-1}[/tex]

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

    [tex]c_{nj} \approx b_j n^{2j}[/tex]

    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):

    [tex]\sum_{k=1}^{n-1} k^q \approx \frac{1}{q+1} n^{q+1}[/tex]

    So that:

    [tex]\begin{align*}b_j n^{2j} &= \sum_{k=j-1}^{n-1} (n-k) b_{j-1} k^{2j-2} \\
    &=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} \\
    &\approx \frac{1}{2j-1} n^{2j} b_{j-1}- \frac{1}{2j} n^{2j}b_{j-1} \\
    &=\frac{1}{(2j)(2j-1)} n^{2j} b_{j-1} \end{align*}[/tex]

    And so:

    [tex]b_{j} = \frac{1}{(2j)(2j-1)} b_{j-1}[/tex]

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

    [tex]b_j= \frac{1}{(2j)!}[/tex]

    [tex]c_{nj} \approx \frac{n^{2j}}{(2j)!}[/tex]

    [tex]a_n \approx \sum_{j=0}^n \frac{n^{2j}}{(2j)!} \alpha^j[/tex]

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

    [tex]\begin{align*}a_{px} &\approx \sum_{j=0}^{px} \frac{{(px)}^{2j}}{(2j)!} \frac{(-1)^j}{p^{2j}}\\
    &=\sum_{j=0}^{px}(-1)^j \frac{x^{2j}}{(2j)!}\end{align*} [/tex]

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

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

    The taylor series for cos(x). Anyone know an easier way?
    Last edited: Jan 26, 2006
  4. Jan 29, 2006 #3


    User Avatar
    Homework Helper

    Oh, you're welcome pokeka. Not a problem. Your thank you made it all worth while...
  5. Jan 30, 2006 #4
    If it's any consolation, I am certainly impressed. :)
  6. Jan 31, 2006 #5


    User Avatar
    Homework Helper

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