Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook