Monday April 9 4:00 - 4:50 PM Kelley 1001
Paul Cull Professor Emeritus School of EECS Oregon State University Fast Fibonacci! Fibonacci numbers have been discussed for nearly a thousand years. For reasonable values of n, the n th Fibonacci number can be efficiently computed by the standard iterative algorithm, based on the Fibonacci recurrence relation. This method uses simple addition. For large values of n, algorithms that use multiplication are faster. We explore a variety of algorithms-- some based on the matrix representation, some based on Lucas numbers, and some based on the Chinese Remainder Theorem. We predict which methods should be fastest. We used Maple to explore the run-times of several multiplication-based methods. We found that predicting run-times was made difficult by the fact that Maple uses a variety of multiplication algorithms, based on the size of the operands. We found that the product of Lucas numbers method is still the fastest known algorithm, although for large numbers, the Two-Term method based on the Chinese Remainder Theorem seems to be competitive. Biography: Professor Paul Cull has been at Oregon State University since 1970. He was one of the founders of the Computer Science Dept. He continues teaching mainly in the areas of algorithms and theory. His most recent papers are in a variety of areas including population models, 3-D vision, and convergence of iterations. He is one of the authors of: Difference Equations: from Rabbits to Chaos Springer, 2005. This talk is based on the work of some of the students in the summer REU program in mathematics and computer science. This program, now in its 20th year, introduces undergraduatesto research and prepares these students for graduate studies.
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
