N的第N个Fibonacci数大到10 ^ 19？

Question

我正在尝试制作一个程序来找到1 <n <10 ^ 19的第n个Fibonacci数.

这是我使用动态编程的代码.

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个斐波纳契数是不可行的(至少我猜它不会起作用).

有一个很多更好的方法来做到这一点.这种技术适用于很多像这样的系列.它被称为斐波那契Q矩阵.

哪里

可以这样想:

你有一些矩阵将矢量A转换成B:

填写这些条目很容易.特殊的部分是它现在是一个矩阵运算符,所以如果我们想要第1000个Fibonacci数,我们只需要进行矩阵乘法.

你可以通过一个循环来做到这一点,但它需要花费你很长时间才能达到10 ^ 19,并且进行10 ^ 19次矩阵乘法(即使它们很小)也需要花费很长时间太.

相反,我们采取另一种捷径.x ^ N可以被重写为它们总和为N的幂的乘积,即

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

因此,目标是在没有进行大量计算的情况下在指数中获得大数字:

x**2和x*x他们一样困难- 他们需要相同的时间.但是x*x*x*x给出相同的答案,(x**2)**2同时需要额外的乘法.当你走向更高的权力时,收益会越来越多.因此,如果你将指数分解为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的函数一样 - 没有递归.现在对我来说已经很晚了,所以我现在不打算输出它.如果有人想看到这一点,请在评论中告诉我,我会将其添加进去.

Answer 2

在O(n)效率下,你永远不会到达那里.与具体代码无关,但Dijkstra的注释"为了纪念Fibonacci"描述了一种在O(log(n))效率中找到F(n)的方法.

F(2n-1)= F(n-1)^ 2 + F(n)^ 2

F(2n)=(2*F(n-1)+ F(n))*F(n)

你不仅可以,但仍然递归.