Fast Fibonacci Transform

For a general second-order 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)\over 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).

References

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