Easiest/Laziest formula for Nth Fibonacci number December 12, 2009Posted by Ragesh G R in Physics and Maths, Uncategorized.
There are many formulae for finding the Nth Fibonacci number, from recursive to non-recursive. Let me try to find the easiest laziest formula.
We know that most of the Fibonacci numbers ( from the 7th ) are in the Golden ratio. Let Golden Ratio (1.618…) be Phi.
Then F(n) = F(n-1)*Phi = F(n-2)*Phi^2 and so on.
So generally F(n) = F(n-x)*Phi^x
But we can’t write F(n) = F(1)*Phi^(n-1), because this will give you inaccurate results , because the 1st 7 numbers do not follow the Golden Ratio.
So the highest value x can take for a fairly accurate determination is n-7.
So our formula becomes F(n) = F(n-(n-7))*Ph^(n-7)
Therefore F(n) = F(7)*Phi^(n-7)
Fibonacci series goes as 1,1,2,3,5,8,13
So F(n) = 13*Phi^(n-7).
This will give a you a fairly accurate value for Nth Fibonacci.
You can get even lazier and say F(n) = 3*Phi^(n-4)
But this will magnify the error for 3 non compliant numbers and give you inaccurate resulsts, but if only it was accurate, this would be better from a laziness perspective if you are programming, because there are only 4 special cases. Of course we can argue that computation of Phi^(n-4) will take fractionally more time than computation of Phi^(n-7), but we can neglect that
Disclaimer : I am sure this already in some literature, but I got this idea when I was in the restoom (a link to my previous post LOL! ), so its mine , he he ! and I could not find similar text by “lazy” googling