斐波那契数列,快速计算.PDF

模型 1 斐波那契数列, 快速计算 斐波那契数列 F , F , F , . . . 由以下关系定义 F0 = 0, F1 = 1, Fn+2 0 1 2 = F + F 其中 n = 0, 1, 2, . . . 显然, F 可以由大约n次算数运算得 n+1 n n 出。 用以下技巧我们可以更快速地计算, 只需大约log n次算术运算 。 构造一个 2 ×2 矩阵 M := 1 1 . 1 0 则 Fn+2 = M Fn+1 , Fn+1 Fn 由此, Fn+1 = M n 1 Fn 0 (用到了矩阵乘法 的结合律). 对于n = 2k ，由多次求平方得到 M n ，其中有k次 2 ×2 矩 阵乘法 。 对于任意n ，把n写成二进制形式n = 2k1 + 2k2 + · · · + 2kt , k1 k2 · · · k , 则M n = M 2k1 M 2k2 · · · M 2kt 。 这 样 至 多 需 要 2kt ≤ 2 log n t 2 次 2 ×2 矩阵的乘法。 1 2 1. 斐波那契数列快速计算 注：相似的技巧可以用于任何由以下递推关系定义的数列 (y , y , y , . . .) ，y = a y + · · · + a y ，其中 0 1 2 n+k k−1 n+k−1 0 n k, a , a , . . . , a 为常数。 0 1 k−1 如果我们想用这个方法计算斐波那契数列, 需要注意F 增长地很 n 快。从下面的模型 2 的一个公式可以看到Fn 的十进制数字的位数为n 阶。所以，我们必须采用多精度运算，运算过程也会相对慢一些。 来源： 这是个众所周知的技巧, 但至今我还没找到有关它的起源的 参考文献