Letter to Dr. Dobb's Journal on Fast Fibonacci Numbers

                                                   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