jump to navigation

Easiest/Laziest formula for Nth Fibonacci number December 12, 2009

Posted by Ragesh G R in Physics and Maths, Uncategorized.
trackback

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

Advertisements

Comments»

1. mithblogsin - December 12, 2009

Sema! It might already be in the literature! Who cares! The credit still completely goes to you! Now both in terms of space and time this is faster than the traditional recursive Fibonacci.Cool! Congrats on the discovery! Next time I have to use a fibonacci algorithm, I’ll use this!

2. Ragesh G R - December 12, 2009

heheh thanks! ya time wise and space wise pretty simple formulae but don’t blame me for any inaccuracies. :-p

mithblogsin - December 12, 2009

hehe! Everything is about trial and error! We’ll see how accurate/inaccurate it is!

Ragesh G R - December 12, 2009

its pretty accurate hebhe

3. BOB - December 12, 2009

another paper from Einstein ..lol

Ragesh G R - December 12, 2009

hehe lol!

4. BOB - December 13, 2009

btw wonder where ppl use fibonacci in programming !!
except 2nd standard kids in West mambalam

Ragesh G R - December 13, 2009

lol! have nt u used? whats with 2nd std kids in west mambalam, fibonacci and golden do not surface till some 6th std

5. Rajita Gupta - March 13, 2015

Find the best books for IIT JEE at 99grades – India’s leading online book-selling company. We have the largest collection of books with latest strategies and tips to prepare and crack the IIT JEE exam.
http://www.99grades.com/shop/BOOKS/competitive-exams/IIT,JEE,Medical%20Exams


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: