[NAFV_P]

Regarding the golden ratio ....

The nth number in Fibonacci sequence is denoted by f(n)

The golden ratio is equal to the limit of f(n)/f(n-1) as n increases without limit.

A recursive implementation of the nth number in the Fibonacci sequence in C:

  unsigned long long fib(int a) {
    return a>1 ? fib(a-1)+fib(a-2) : 1;
  }

The above function can take a while to execute if a is sufficiently large, on my machine fib(40) takes about a second to return a value.

Time taken to execute the function fib(a) is denoted by t(a).

As n increases without limit t(n)/t(n-1) approaches the golden ratio.

In practise this should give you a rough value of the golden ratio.

The reason this happens is because the function can only increase the return value by unity, one call at a time.

[ipsin]

What's interesting to me is that you can demonstrate this without too much work, and it's true for starting numbers other than 1,1, such as Lucas numbers (1,3,4,7,11,...)

f(n+2)=f(n+1)+f(n)

If you posit that this number has a solution in f(n)=a^x, you see that

a^(n+2)=a^(n+1)+a^n

Dividing by a^n, you get a^2=a+1, a simple quadratic with two roots, (1+sqrt(5))/2 and (1-sqrt(5))/2, or the golden ratio and approximately -0.618.

Because any constant multiple of the function will also solve the equation, a solution to f(n) will be some linear combination of f(n)=c1(1.618..)^n+c2(-0.618)^n, for constants c1 and c2. You calculate c1 and c2 to match your initial conditions.

As n increases, the second term tends to 0, so f(n+1)/f(n) approaches the golden ratio.

[NAFV_P]

> What's interesting to me is that you can demonstrate this without too much work, and it's true for starting numbers other than 1,1, such as Lucas numbers (1,3,4,7,11,...)

Your comment reminded me of chaos theory, small changes in initial conditions can have a radical effect upon the final outcome. In this case it seems to be the opposite.

> Because any constant multiple of the function will also solve the equation, a solution to f(n) will be some linear combination of f(n)=c1(1.618..)^n+c2(-0.618)^n, for constants c1 and c2. You calculate c1 and c2 to match your initial conditions.

Bear with me a second, I have to fish out an old geometry book...

"Geometry", Roger Fenn, Springer-Verlag 2001, page 24:

I've got it, the equation you gave is very similar to Binet's Formula:

http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...

[sp332]

Well, that's because it's an awful way to calculate a fibonacci number! At least you could memoize the function, remembering what the (n-1) number was instead of recalculating every time. Or, since you only need the last 2 numbers to keep going, forget everything but those 2:

  unsigned long long fib(int a) {
      unsigned long long x, y, temp;
      while (a > 0) {
          temp = x;
          x = y;
          y = y + temp;
          --a;
      }
      return y;
  }

This is much faster and won't blow up your stack.

[NAFV_P]

> Well, that's because it's an awful way to calculate a fibonacci number!

To be more precise, it is an inefficient method of calculating a Fibonacci number. Using your function, if you were to measure the execution time of fib(n), then divide it by the execution time of fib(n-1), would you get a more precise value of the Golden ratio?

> This is much faster and won't blow up your stack quite so much.

Or we could use an iterative version ... wait up your code changed to an iterative implementation. Man that's weird.

EDIT:

Your code:

  unsigned long long fib(int a) {
    unsigned long long x, y, temp;
    while (a > 0) {
      temp = x;
      x = y;
      y = y + temp;
      --a;
    }
    return y;
  }

I just noticed: x, y and temp have not been initialised.

[sp332]

I have to admit, I did not understand your earlier comment until just now.

Sorry about the code change, the first version was from an old memory and the new version is what happened after I stared at it for a while :) Primitive values are automatically initialized to 0 in C. As for the ratio, it will probably just give a good approximation of 1 as a gets large! Also if you have a good square root function, you can use it to find a Fibonacci number in constant time, so your ratio will always be 1 (until the square root is too big to be computed in a single instruction).

[mattst88]

> Primitive values are automatically initialized to 0 in C.

No, they're not. Automatic variables without an initializer have an indeterminate value. See http://stackoverflow.com/questions/6212921/is-un-initialized...

[NAFV_P]

> I have to admit, I did not understand your earlier comment until just now.

From the number of downvotes, I think it was mis-parsed by several HN readers. This happens to me quite often, on many a website, but I have no inkling why.

> Sorry about the code change, the first version was from an old memory and the new version is what happened after I stared at it for a while

No worries, I thought the original slice of code that you posted was more interesting and novel, it wouldn't have occurred to me off the top of my head.

> Primitive values are automatically initialized to 0 in C.

I had to look that up, good old Stack Overflow has again furnished us with an explanation.

http://stackoverflow.com/questions/10089551/what-are-primiti...

[sp332]

Oh, C, C++, what's the difference. (D'oh!)

[NAFV_P]

One of the reasons I stick to old C, less confusion.

[TheLoneWolfling]

Why not just directly get an approximation of the golden ratio by taking fib(n) / fib(n-1)?

If you use an iterative / tail-recursive version you can actually do this directly, without even the overhead of having to calculate it twice.

(I.e. define fib to return a tuple / struct / etc consisting of (fib(n), fib(n-1)).)

[NAFV_P]

> Why not just directly get an approximation of the golden ratio by taking fib(n) / fib(n-1)?

That has been done millions of times over the past 800 odd years. My method has no practical uses, but plenty of educational ones.

[JadeNB]

> Time taken to execute the function fib(a) is denoted by t(a).

This function has a name: t(a) = fib(a) (up to some fiddling with constants, depending on how you count execution 'time').

[NAFV_P]

> This function has a name: t(a) = fib(a) (up to some fiddling with constants, depending on how you count execution 'time').

I was thinking of either time() or gettimeofday() from the standard and POSIX libraries respectively.

[radicality]

Where are you getting at with the the t(n)? As you said, the golden ratio is defined as the limit of f(n+1)/f(n), and yes, with this implementation (because f ~ t) t(n+1)/t(n) also converges to the golden ratio, but... so what, why not just use f ?

[NAFV_P]

It's been done before. Calculating the golden ratio using your method provides insights into the world of mathematics. My method provides insights into the world of programming.