Harry J. Smith < C O P Y > 19628 Via Monte Dr. Saratoga, CA 95070 May 25, 1991 Letter to the Editor Dr. Dobb's Journal M & T Publishing, Inc. 501 Galveston Dr. Redwood City CA 94063 Fast Fibonacci Numbers Dear DDJ, Victor J. Duvanenko's "Efficiently Raising Matrices to an Integer Power" (June 1991) showed me that the method I have been using for raising real numbers to integer powers can also be used for matrices. I call this the "Russian peasant method" for exponentiation. It is closely related to a method of that name for multiplication which only involves the simple operations of halving, doubling, and adding. While this is an efficient method of raising a matrix to an integer power, it is not an efficient method of computing Fibonacci numbers as was implied in the article. There is an exact equation for Fibonacci numbers due to Jacques Philippe Marie Binet published in 1843: F(n) = (b^n - c^n)/a where a = Sqrt(5), b = (1 + a)/2 = Golden Ratio, c = (1 - a)/2 = 1 - b = -1/b. Since the magnitude of c^n/a is less than 1/2 for n >= 0, an efficient method of computing Fibonacci numbers is the evaluation of the equation: F(n) = Round(b^n / a). In C this can be programmed as: #include <math.h> fib = floor(0.5 + pow(b,n)/a); A program based on this method runs 15 to 20 times faster than Victor's matrix method. Harry J. Smith

Return to Harry's Home Page

This page accessed times since October 20, 2004.

Page created by: hjsmithh@sbcglobal.net

Changes last made on Saturday, 14-May-05 12:47:07 PDT