A Fibonacci number refers to a term in a sequence with a recurrence relationship based on the previous two terms of the sequence. More specifically, a given number in the sequence is equal to the sum of the two previous terms. The first two terms are both 1, which yields the sequence { 1, 1, 2, 3, 5, 8, 13, ... }
I had thought that this sequence was first used to describe the breeding characteristics of a rabbit population, but it appears that, according to the
Wikipedia entry on Fibonacci numbers that its usage and application go back farther than that.
At any rate, the generation of the Nth term of the fibonacci sequence is a decent exercise in basic programming techniques. Since it is defined as a recurrence relation with a base case, it is quite natural to express it as a recursive function:
// C++ and similar
unsigned int nthFib(unsigned int n) {
if (n == 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
return nthFib(n-1) + nthFib(n-2);
}
This code fudges the value for 0, since a Nth-term ordering starting at 1 should not have a 0th element. At any rate, it provides a basic recursive solution to finding the Nth Fibonacci number.
There's a problem with this approach. Each call with N as the input while N is greater than 2 is going to make two new calls, for N-1 and N-2. Each of those will make two new calls, and so on. This approach repeatedly recalculates Fibonacci numbers that have already been computed. The number of wasted calculations grows factorially, which quickly becomes too slow to be useful. For example, to calculate the 20th fibonacci term, we hit our base case (n == 1 or n == 2) over 6,700 times with a total number of computer terms over 13,500.
There are various ways to speed this up, such as caching intermediate terms and only calculating them as needed. We can modify the original code as follows:
std::map<unsigned int, unsigned int> fibCache;
unsigned int nthFib2(unsigned int n) {
if (n == 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
std::map<unsigned int, unsigned int>::const_iterator loc
= fibCache.find(n);
unsigned int result;
if (fibCache.end() == loc) {
result = nthFib2(n-1) + nthFib2(n-2);
fibCache.insert(std::make_pair(n, result));
} else {
result = loc->second;
}
return result;
}
This code, in contrast, only makes N+1 computations to determine the Nth Fibonacci number. However, this approach has limitations as well. We still have to store every previous value used to compute the Nth term, even if all we care about is the Nth term.
There's another approach to generating Fibonacci numbers, which is an iteratative approach rather than recursive. If you notice that any given Fibonacci number is equal to the sum of the two previous terms, it follows that we should be able to compute the Nth term in an iterative fashion by keeping track of the current term and the two previous terms, and repeatedly generating the next term by replacing the N-2 term with the new N.
unsigned int nthFib3(unsigned int n) {
if (n == 0) {
return 0;
}
unsigned int seq[3] = {1, 1, 1};
for (int i=2; i<n; ++i) {
seq[i % 3] = seq[(i - 1) % 3] + seq[(i - 2) % 3];
}
return seq[(n - 1) % 3];
}
It is evident from this code that it will make exactly n - 2 computations.
Both this approach and the cached recursive approach suffer from limitations in the range of numbers representable using standard machine (primitive) types. The 45th and 46th Fibonacci numbers are 1,134,903,170 and 1,836,311,903, respectively. The 47th term, however, is 2,971,215,073, which is beyond the range of a 32-bit signed integer. Using an unsigned integer only gets you one more term. Using a 64-bit integer gives you up to 92 terms. Clearly, arithmetic operations on standard types do not scale well when you're doubling the value about every two and a half terms.
To go beyond the limits of standard machine types, you could either use a large integer type, such as Java's BigInteger, or you can use an approximation algorithm. The ratio between sequential terms of the sequence approaches φ (Phi - the
golden ratio). This can be used to calculate larger values of the Fibonacci sequence directly without relying on calculating all prior terms of the sequence. See the
Wikipedia entry on the Fibonacci sequence for these formulae.
So what's the fastest way to get the Nth Fibonacci number? Well, any algorithm used to generate the numbers is going to quickly run into boundaries based on the limits of the size of integers your system can process. Therefore, I think it's preferable to pre-compute all the values you will use and store them in a lookup table. This will give you O(1) access to the Nth Fibonacci number, for any N you have precomputed.
