Skip to content

Fibonacci numbers

August 31, 2013

Writing a method that calculates a particular Fibonacci number is still a frequently used programming exercise during interviews. During interviews, the test is of simple programming ability, but there are a variety of ways to solve this problem ranging from exponential to sub-linear with respect to the number in the sequence desired.

Typical solutions: Exponential to Linear

The typical solution to this problem given is one of two options: either recursively solving in exponential time (O(2^n)) or linear (O(n)) where “n” is the number in the sequence. The recursive solution can further be optimized to O(n) running time with an addition of O(n) extra storage by using memoization. In the implementations below note the use of java.util.BigInteger since Fibonacci numbers can overflow ints and longs very quickly. These 3 versions of fibonacci are implemented below in Java:

More advanced and efficient solutions

Fibonacci numbers can actually be found much faster than linear. There exists a logarithmic solution just as capable as the algorithms above, and there even exists a constant time solution that works but is extremely limited by precision. Here is the code for both the logarithmic solution in Java:

The logarithmic algorithm was implemented using Dijkstra’s algorithm. There also exists a constant time O(1) function that calculates Fibonacci numbers by relying on the fact that the ratio of F(n+1)/F(n) converges to the golden ratio as n approaches infinity. Binet’s formula for calculating fibonacci numbers.

Advertisements

From → Algorithms

Leave a Comment

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: