TOPICS
Search

Fast Fibonacci Transform

For a general second-order linear recurrence equation

f_(n+1)=xf_n+yf_(n-1),
(1)

define a multiplication rule on ordered pairs by

(A,B)(C,D)=(AD+BC+xAC,BD+yAC).
(2)

The inverse is then given by

(A,B)^(-1)=((-A,xA+B))/(B^2+xAB-yA^2),
(3)

and we have the identity

(f_1,yf_0)(1,0)^n=(f_(n+1),yf_n)
(4)

(Beeler et al. 1972, Item 12).

Explore with Wolfram|Alpha

References

Gosper, R. W. and Salamin, G. Item 12 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 6, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html#item12.

Referenced on Wolfram|Alpha

Fast Fibonacci Transform

Cite this as:

Weisstein, Eric W. "Fast Fibonacci Transform." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FastFibonacciTransform.html

Subject classifications