主題
Search

快速斐波那契變換

對於一般的二階 線性遞推方程

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

透過下式定義有序對上的乘法規則

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

則逆運算由下式給出

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

我們有恆等式

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

（Beeler等人，1972年，專案12）。

使用 探索

參考文獻

Gosper, R. W. 和 Salamin, G. Beeler, M.; Gosper, R. W.; 和 Schroeppel, R.HAKMEM. Cambridge, MA: MIT 人工智慧實驗室備忘錄 AIM-239, p. 6, 1972年2月中的專案 12。 http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html#item12。

在 中被引用

快速斐波那契變換

請引用為

Weisstein, Eric W. “快速斐波那契變換。” 來自 Web 資源。 https://mathworld.tw/FastFibonacciTransform.html

主題分類