python - n 的第 N 个斐波那契数等于 10^19？

Question

我正在尝试编写一个程序来查找 1 < n < 10^19 的第 n 个斐波那契数。

这是我使用动态规划的代码。

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 2:
        f = 1
    else:
        f = fib(n-1) + fib(n-2)
    memo[n]=f
    return f
print fib(input()) % 1000000007

我的代码似乎不适用于大量数据。我收到无效响应错误。 有什么建议吗？

Answer 1

当 N 为 10^19 时获得第 N 个斐波那契数如果你以天真的方式去做是行不通的(至少我猜它行不通)。

有一种好得多的方法来做到这一点。这种技术适用于很多像这样的系列。它叫做 Fibonacci Q Matrix .

在哪里

可以这样想:

你有一些矩阵将向量 A 转换为 B:

填写这些条目很容易。特殊之处在于它现在是一个矩阵运算符，所以如果我们想要第 1000 个斐波那契数，我们只需要进行矩阵乘法。

你可以用一个循环来做到这一点，但是你要花很长时间才能达到 10^19，而做 10^19 矩阵乘法(即使它们很小)也需要也有一段时间。

相反，我们走另一条捷径。 x^N 可以重写为幂的乘积，它们总和为 N，即

x**100 == x**90 * x**10

因此，目标是在不进行大量计算的情况下在索引中获取大量数字:

x**2 与 x*x 一样难 - 它们花费的时间相同。但是 x*x*x*x 给出与 (x**2)**2 相同的答案，同时需要额外的乘法。当您获得更高的权力时， yield 会增加。因此，如果您将指数分解为 2 的幂(任何幂都有效，但这是最简单的情况)，

X**100 == X**64 * X**32 * X**4

即

X**100 == (((((X**2)**2)**2)**2)**2)**2 + ...

所以您要做的是计算您想要达到的总功率的两个幂，然后取 Q 矩阵的两个幂的乘积。

这似乎对我有用:

fib_matrix = [[1,1],
              [1,0]]

def matrix_square(A, mod):
    return mat_mult(A,A,mod)


def mat_mult(A,B, mod):
  if mod is not None:
    return [[(A[0][0]*B[0][0] + A[0][1]*B[1][0])%mod, (A[0][0]*B[0][1] + A[0][1]*B[1][1])%mod],
            [(A[1][0]*B[0][0] + A[1][1]*B[1][0])%mod, (A[1][0]*B[0][1] + A[1][1]*B[1][1])%mod]]


def matrix_pow(M, power, mod):
    #Special definition for power=0:
    if power <= 0:
      return M

    powers =  list(reversed([True if i=="1" else False for i in bin(power)[2:]])) #Order is 1,2,4,8,16,...

    matrices = [None for _ in powers]
    matrices[0] = M

    for i in range(1,len(powers)):
        matrices[i] = matrix_square(matrices[i-1], mod)


    result = None

    for matrix, power in zip(matrices, powers):
        if power:
            if result is None:
                result = matrix
            else:
                result = mat_mult(result, matrix, mod)

    return result

print matrix_pow(fib_matrix, 10**19, 1000000007)[0][1]

然后，您可以更进一步 - 它只是一个 2x2 矩阵，所以我们可以对角化它，然后得到第 n 个斐波那契数的公式，就像 n 的函数 - 没有递归。像这样:

如上所述，我们计算从一步到下一步的矩阵:

然后是从一组数字到下一组数字的关系:

我们可以在哪里链接这些矩阵乘法:

没有什么可以阻止我们一路回到第一个斐波那契数列:

现在游戏变成了“我们如何提高该矩阵的 n 次方”——这正是上面代码中所做的。但是有比我上面提出的解决方案更好的方法。我们可以将 Q 矩阵分解为特征值和向量，这样写:

其中 U 是包含 Q 特征值的酉矩阵，< em>Λ 是对应特征值的矩阵。这些特征值和向量是:

然后您使用这种分解方式的标准优势之一，当您将其提升为一个幂时，相邻的 U 矩阵及其逆矩阵将组合为酉矩阵，留下单个 U 及其逆矩阵在末端，中间有一串对角矩阵，将它们提升为幂是微不足道的:

因此，现在我们拥有了根据单个公式编写第 n 个斐波那契数所需的一切，无需递归。我会在明天/本周晚些时候完成它...