Saturday, March 17, 2012

Fibonacci number calculation algorithms

There are many blogs and websites provided excellent solutions for nth Fibonacci number calculation.

Fibonacci number
Different algorithms varies from O(n2) to O(n) to O(logn).

details can be found in below examples:

From the wikipedia, , we know that nth Fibonacci number satisfy this math equations:
As you can see that if we keep a careful pre-calculated Fibonacci numbers in memory, a (m+n)th Fibonacci number can be calculated with combinations of mth and nth Fibonacci numbers. If mth and nth Fibonacci numbers are not in the pre-calculated map, we can further search down the chain.

I feel that if we can have a carefully selected array of pre-calculated Fibonacci numbers, we can easily achieve at worst O(logn) while at best O(1) performance without sacrifice of accuracy as following formula does:
a close estimation, accuracy becomes worse while n grows bigger
As a common approach, preparation of certain information as part of the data structure designed can speed up performance exponentially. This approach is also part of our Unix/Linux culture that we prefer complex data structures than complex algorithms in source codes.

No comments:

Post a Comment