3 ms·

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 w

by NAFV_P 12y ago

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 12y ago
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 12y ago
  > 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.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
JadeNB 12y ago
> 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 12y ago
  > 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.
sp332 12y ago
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 12y ago
  > 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 12y ago
    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).
    - NAFV_P 12y ago
      > 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-primitive-types-default-initialized-to-in-c http://stackoverflow.com/questions/10089551/what-are-primiti...
radicality 12y ago
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 12y ago
  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.

by NAFV_P 12y ago

ipsin 12y ago

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 12y ago
> 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.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...

JadeNB 12y ago

> 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 12y ago
> 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.

sp332 12y ago

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 12y ago
> 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 12y ago
  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).
  - NAFV_P 12y ago
    > 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-primitive-types-default-initialized-to-in-c http://stackoverflow.com/questions/10089551/what-are-primiti...

radicality 12y ago

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 12y ago
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.