Hacker News new | past | comments | ask | show | jobs | submit login

There's a closed form solution to calculate the Nth Fibonacci number which can be derived from a recurrence relation.

http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_e...




Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.


Ah my mistake then. I didn't realize the closed form solution takes that long to evaluate.

Couldn't there be a faster way to evaluate it using an algebraic rather than a computational way? I just find the bound you give too high but I may be completely wrong.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: