主题
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）。

使用 Wolfram|Alpha 探索

参考文献

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。

在 Wolfram|Alpha 中被引用

快速斐波那契变换

请引用为

Weisstein, Eric W. “快速斐波那契变换。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/FastFibonacciTransform.html

主题分类