Fast Fibonacci Numbers

Volume 2, Issue 3
Summer 1992

A recursive formula giving the Fibonacci number f_2n in terms of f_n and f_n-1 forms the basis for efficient computation of large Fibonacci Numbers. Mathematica can be used to derive other recursive formulas that generalize this "reduction by halves." The additional formulas lead to algorithms that improve performance in certain cases.