info prev up next book cdrom email home

Fast Fibonacci Transform

For a general second-order recurrence equation

\end{displaymath} (1)

define a multiplication rule on ordered pairs by
\end{displaymath} (2)

The inverse is then given by
(A,B)^{-1}={(-A,xA+B)\over B^2+xAB-yA^2},
\end{displaymath} (3)

and we have the identity
\end{displaymath} (4)

(Beeler et al. 1972, Item 12).


Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

© 1996-9 Eric W. Weisstein