Geek Answers Handbook

Fibonacci Recursion Using Golden Ratio (Golden Number)

I can make a recursive function to calculate the nth Fibonacci term as follows:

int rec (int i) { if(i == 1 || i == 2) return i; else return rec(i-1)+rec(i-2);

}

But I want to use the golden number, which is 1.618 for Fibonacci calculation; but my attempt failed, I am wrong:

 int rec (int i) { if(i == 1 || i == 2) return i; else return 1.618*rec(i-1); }

How can I make it work?

+4
source share
5 answers

The golden ratio is an irrational number , so you should not necessarily expect that you can connect it to the formula to get an accurate result.

If you want to know how to quickly calculate the number n th fibonacci, here is a page that lists the various methods in decreasing order of execution time (but increases in order of complexity of implementation): http://www.nayuki.io/page/fast-fibonacci -algorithms

+8
source

If you are referring to the Binet Formula , do something like this:

 long fib(int i) { double phi = // Golden Ratio return Math.round((Math.pow(phi, i) - Math.pow(-phi, -i)) / Math.sqrt(5)); }

Please note that the above formula is not recursive. I do not know any recursive formulas for calculating fib. using the golden ratio.

+1
source

Here's how you do it:

 double gr = 1.618033988749895; double FibGoldenRatio(int i) { if (i == 1 ) return 1; return Math.Round(gr * FibGoldenRatio(i - 1)); }

Here's an example output:

 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1.30496954492866E+15
+1
source

Your math seems to be wrong, and you round too often. I used this formula .

It works:

 double gr = 1.618033988749895; int rec (int i) { return (int)round(rec2(i)/(gr+2)); } double rec2 (int i) { if (i == 1) return gr; else return gr*rec2(i-1); }

Furthermore, this does not have to be recursive:

 static int rec (int i) { return (int)round(pow(gr, i)/(gr+2); }

I did not check too many numbers, but turned out to be pretty accurate (Java) .

0
source

You can calculate the gold ratio yourself and use it to find the nth Fibonacci number.

 long long fib(int n) { double phi = (1 + sqrt(5))/2.0; // golden ratio double phi_hat = (1 - sqrt(5))/2.0; // fraction part of golden ratio return (pow(phi, n) - pow(phi_hat, n))/sqrt(5); }
0
source

More articles:


All Articles