Date: 2000 Jan 11
My coauthors and I are presenting a paper entitled ``Accurate Approximations for Asian Options'' at the Symposium on Discrete Algorithms conference so I will not be with you today. I will return to San Antonio tomorrow afternoon.
The sequence of Fibonacci numbers begins 0, 1, 1, 2, 3, 5, 8, 13, 21, .... In general, the Fibonacci numbers can be defined by the rule
Today's group project is to implement Fibonacci numbers three different ways. This will demonstrate how different algorithms solving the same problem require different times.
The recursive definition appears in the Introduction. Implement it recursively.
Directly using the recursive definition is wasteful because many Fibonacci numbers are computed repeatedly. For example, when computing , is computed once, is computed twice, is computed three times, and is computed five times. (The number of computations is a Fibonacci sequence in itself!)
We can greatly reduce the running time by storing the result of computing each number. For example, when computing , we must compute . When we do so the first time, we can store its value in the third position of an array. Thus, when computing , we check if it has already been computed. If so, we have the answer. Otherwise, we (recursively) compute the answer, store it, and then return it. This should greatly reduce the running time, but we need an array with potentially infinite size because we do not know a priori how large a Fibonacci number we need to compute.
First, convince yourself that, when computing using this scheme, we will store , , , ..., , in that order.
Second, we note that storing these values in an array will not work because we cannot guarantee the array will be large enough. Instead, we can turn to our friend the Standard Template Library. (For the rest of this section, we will assume the Fibonacci function returns a value of type long double. See below.)
A vector<long double> is an array of long doubles that can grow when needed.
The vector of Fibonacci numbers could be a global variable, but avoiding global variables is usually a good idea. One approach is to package together the vector and the Fibonacci function in a class. Another approach is to define the Fibonacci function with a static vector (if you know what that means).
When timing this implementation, be sure to start the program with an empty vector to be fair to the other implementations.
Édouard Lucas discovered a formula for the Fibonacci numbers:
The floor function x yields the smallest integer less than or equal to x. For example, 7.4 = 7 = 7.
The Gnu C Library may be useful when implementing this algorithm.
Assume we wish to compute for nonnegative n only. If you desire, you can use unsigned longs for both the parameter and the return type. Using a return type of doubles or long doubles will extend the domain for which Fibonacci numbers can be computed. This is necessary for the linear and constant time algorithms. For example, the function declaration could be
To time your code, we add a function to print the running time of your program.
The smallest unit of time most computers running Linux is 10 msec so the data may be noisy for small running times. To tell the compiler to produce very optimized code, use the -O3 compiler code. For example,
Use your favorite graphing package or Microsoft Excel to produce plots comparing n and the time to compute . Try to find an equation and its R2 value for the running times. What does the R2 value mean?
I am not a regular Microsoft Excel user, but here are some tips I found useful.
Leonardo Fibonacci2 (c. 1170-c. 1240) introduced Fibonacci numbers in 1202. Édouard Lucas popularized the term ``Fibonacci numbers.'' These numbers occur so frequently in mathematics that an entire journal named Fibonacci Quarterly exists.
Fibonacci numbers can model the number of pairs of rabbits on an island. Initially, a pair (male and female) of newborn rabbits is placed on an island. Each sexually mature pair of rabbits can breed every month, but newborns must wait two months to become mature. At the beginning (just before the rabbits are placed on the island), there are no pairs of rabbits ( ). At the end of the first and second months, there is still one pair of rabbits ( ). Then they give birth to a pair of rabbits ( ). The next month, the original pair gives birth to another pair of rabbits, but the second pair is not yet sexually mature ( ). The next month the second pair of rabbits are mature so two pairs of rabbits give birth ( ). The process continues.