当N为10^19时,如果你采用朴素的方式获取第N个斐波那契数是行不通的(至少我猜测它不会行得通)。
有一种更好的方法来做这件事。而且这种技巧适用于许多类似的序列。它被称为
Fibonacci Q Matrix。
![enter image description here](https://istack.dev59.com/KbyvF.gif)
在哪里
![enter image description here](https://istack.dev59.com/GNgvR.gif)
请这样想:
您有一个将向量A转换为B的矩阵:
![enter image description here](https://istack.dev59.com/xoWRh.webp)
填写这些条目很容易。特别之处在于,现在这是一个矩阵运算符,因此如果我们想要第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
相同的答案,同时需要额外进行一次乘法。随着幂次数的增加,收益会更多。因此,如果将指数拆分为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):
if power <= 0:
return M
powers = list(reversed([True if i=="1" else False for i in bin(power)[2:]]))
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的函数 - 没有递归。就像这样:
与上述类似,我们计算将我们从一步带到下一步的矩阵:
![enter image description here](https://istack.dev59.com/KbyvF.gif)
然后是从一个数字集合到另一个数字集合的关系:
![enter image description here](https://istack.dev59.com/gWBf2.webp)
我们可以在这里链式进行矩阵乘法:
![enter image description here](https://istack.dev59.com/9vtOw.webp)
如果没有任何限制,我们可以一直回溯到第一个斐波那契数。
![enter image description here](https://istack.dev59.com/gqdGY.webp)
现在游戏变成了“如何将那个矩阵乘以n次方”的问题——这正是上面代码中所做的。但是比我提出的解决方案更好的方法是,我们可以将Q矩阵分解为特征值和向量,并将其写成如下形式:
![enter image description here](https://istack.dev59.com/BirhS.webp)
其中U是包含Q的特征值的酉矩阵,Λ是相应特征值的矩阵。这些特征值和特征向量为:
![enter image description here](https://istack.dev59.com/uRhQd.webp)
![enter image description here](https://istack.dev59.com/xf5mr.webp)
然后,您可以利用这种分解风格的标准优势之一,将其提升到幂次方时,相邻的U矩阵及其逆矩阵组合在一起形成幺正矩阵,留下单个U及其逆矩阵在两端,并在中间形成一系列对角矩阵,对这些矩阵进行乘方运算非常容易:
![enter image description here](https://istack.dev59.com/HPkS7.webp)
现在,我们已经拥有所有需要的内容来仅通过一个公式写出第 n 个斐波那契数,无需使用递归。不过我会在明天/本周晚些时候完成它...
1000000007
,而不是实际的斐波那契数。你还可以研究Fib(2n)和Fib(2n+1)的公式,这些公式用Fib(n)和Fib(n+1)表示(例如)。 - Mark Dickinson