Threaded Mode | Linear Mode

***drdebcol*** · (This post was last modified: 08-26-2010 03:20 AM by drdebcol.)

You already know about Fibonacci sequence. Each number of Fibonacci sequence is the sum of the previous two numbers, starting with 0 and 1.
About Fibs you have at Wikipedia :
http://en.wikipedia.org/wiki/Fibonacci_numbers
The sequence begins :

Code:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 and so on.

But there is one interesting thing about Fibonacci numbers.
The higher up in the sequence, the closer two consecutive Fibonacci numbers of the sequence divided by each other will approach the "golden ratio" (approximately 1 : 1.618 or 0.618 : 1).
The golden ratio was used widely in the Renaissance in paintings.
Famous Renaissance painters were painting things depending on this ratio.
About "golden ratio" you have here :
http://en.wikipedia.org/wiki/Golden_ratio

Code:

a(n+1)/a(n) = 1.618

So the task is to write a code that will generate "golden ratio" depending on decimals or better said included EPS.
EPS is accuracy and it is difference between two iterations :

Code:

a(n+2)/a(n+1)-a(n+1)/a(n)>EPS

I defined EPS in the top of the code on 4 decimals :

Code:

#define EPS 0.0001

So "golden ratio" accuracy would be 4 decimals.
So here is the code in C :

Code:

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define EPS 0.0001

int main()

{

  unsigned long f1=0,f2=1,k;

  double dif;

  do

   {

    dif=double(f2)/double(f1);

    k=f2;

    f2+=f1;   

    f1=k; 

  }

  while (fabs(double(f2)/double(f1)-dif)>EPS);

  printf("%lf",double(f2)/double(f1));

system("pause");    

}

***Back_track*** · 08-16-2010, 06:58 AM

A bit above my head..but i get the general idea. Thanks for the contribution.

***drdebcol*** · (This post was last modified: 08-16-2010 08:47 AM by drdebcol.)

(08-16-2010 06:58 AM)Back_track Wrote: A bit above my head..but i get the general idea. Thanks for the contribution.

Well there is a bit of maths in this. Some knowledge about Calculus can help in understanding this task.
Though, when you look at it from a programmers point of view, it is just a do . . while loop.

***Back_track*** · 08-16-2010, 10:28 AM

Yeah, I understood the programs flow. It was just I don't have any calc. knowledge.

***drdebcol*** · (This post was last modified: 08-26-2010 03:21 AM by drdebcol.)

After doing some research i have found better way to calculate Golden ratio, and that is not by using Fibonacci numbers, it is "Newton's method" known as "Newton's iteration" which i used for computing square roots here :
http://www.pro9ramming.com/square-root-c...-1159.html
More about Newton's method you have on Wikipedia :
http://en.wikipedia.org/wiki/Newton%27s_method
Now let's see how this method works.
Golden ratio (=1,61803 etc.) is the largest root of this polynomial :
[Image: 77027_goldenratioequation.png]

When we include this into Newton's method, it should look like :
[Image: 77028_goldenratioequation2.png]

As you can see there are derivatives, so don't try to understand this without knowledge of calculus.
Now when we have x(k+1), we need x(0) which is in this case 1.
That is enough to calculate golden ratio depending on certain EPS
which is in our case :

Code:

EPS = 0.0001

And that is accuracy on 4 decimals (because we have 4 decimals after the dot).
Now i'll live demonstrate why this method has faster convergence (bigger speed) than Fibonacci numbers method explained above.
First i'll post a bit modified code for Fibonacci numbers method :

Code:

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define EPS 0.0001

int main()

{

  unsigned long f1=0,f2=1,k,br=0;

  double dif;

  do

   {

    br++;

    dif=double(f2)/double(f1);

    k=f2;

    f2+=f1;   

    f1=k; 

    printf("%d = %lf\n",br,double(f2)/double(f1));

  }

  while (fabs(double(f2)/double(f1)-dif)>EPS);

  printf("%lf\n",double(f2)/double(f1));

system("pause");    

}

When you compile this code which represent Fibonacci numbers method,
you'll get this (form - iteration = calc_on_that_iteration):
[Image: 77033_goldenratiofibsmethod.jpg]

[Image: 77033_goldenratiofibsmethod.jpg]

As you can see, calculation of Golden ratio on 4 decimals (=1.6180) took 12 iterations (3rd decimal on 10th iteration).
And now Newton's method code :

Code:

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define EPS 0.0001

#define sqr(x) (x)*(x)

int main()

{

  unsigned br=0;

  double x1=1,x2=2;

  do

  {

    br++;

    x1=x2;

    x2=(sqr(x1)+1)/(2*x1-1);

    printf("%d = %lf\n",br,x1);

  }

  while (fabs(x2-x1)>EPS);

  printf("%lf\n",x1);

system("pause");    

}

When you compile it, you'll get :
[Image: 77034_goldenrationewtonsmethod.jpg]

As you can see, 4th decimal is reached at 4th iteration (3rd decimal too).
After running tests on more decimals, Newton's method proved that it is faster (has smaller complexity).
To sum up, Fibonacci number method is interesting because of relation to Number theory, and it is accurate, but slow. Newton's method proved in this case (and in many cases not concerning this), that it is really fast and that it can calculate golden ratio in small number of iterations (depending on how much decimals you want).