n的第N个斐波那契数等于10 ^ 19？ [英] Nth Fibonacci number for n as big as 10^19?
问题描述
我正在尝试编写一个程序，以找到1≤的第n个斐波那契数。 n ＜ 10 ^ 19。
这是我使用动态编程的代码。
memo = {}
def fib（n）：
如果在备忘录中为n：
返回备忘录[n]
如果n< = 2：
f = 1
else：
f = fib（n-1）+ fib（n-2）
memo [n] = f
return f
print fib（input（） ）％1000000007
我的代码似乎不适用于大量代码。我收到无效的响应错误。
有任何建议吗？
如果N为10 ^ 19，则获得第N个斐波那契数对您来说是行不通的
有一种很多更好的方式来做到这一点（至少我想这是行不通的）。这种技术适用于许多类似的系列。它称为
我们可以在其中链接这些矩阵乘法：
没有什么可以阻止我们回到第一个斐波那契数字：
现在游戏变成我们如何将矩阵提高到n次幂-这正是上面代码中所做的。但是有比我上面提出的解决方案更好的方法。我们可以将Q矩阵分解为特征值和向量，如下所示：
其中 U 是一个包含 Q 特征值的单一矩阵strong>和 Λ 是对应特征值的矩阵。这些特征值和向量是：
然后，您使用这种分解方式的标准优势之一，当您将其提升为幂时，相邻的U矩阵及其逆组合得到单一矩阵，剩下一个U并在其末尾逆，中间是一连串对角矩阵，将这些矩阵求幂是很简单的：
因此，我们现在只需要一个公式即可编写第n个斐波那契数，而无需递归。我明天/本周晚些时候会完成它。
I am trying to make a program to find the nth Fibonacci number for 1 < n < 10^19.
Here is my code using dynamic programming.
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
My code does not seem to work for large numbers. I get invalid response error. Any suggestions?
Getting the Nth fibonacci number when N is 10^19 is not goign to work if you do it the naive way (at least i would guess it won't work).
There's a much better way to do it. And this technique works with lots of series' like this. It's called the Fibonacci Q Matrix.
Where
Think of it like this:
You have some matrix which transforms vector A into B:
Filling in those entries is easy. The special part is that this is now a matrix operator, and so if we want the 1000th Fibonacci number, we just need to do matrix multiplication.
You could do this with a loop, but it's going to take you quite a while to get all the way up to 10^19, and doing 10^19 matrix multiplications (even when they're small) is going to take a fair while too.
Instead, we take another shortcut. x^N can be rewritten as the product of power where they sum to N, i.e.
x**100 == x**90 * x**10
So the aim is to get large numbers in the indices without doing lots of calculations:
x**2 is just as difficult as x*x - they take the same amount of time. But x*x*x*x gives the same answer as (x**2)**2 while requiring an extra multiplication. The gains get more as you go to higher powers. So if you break down the exponent into powers of 2 (any power works, but this is the simplest case),
X**100 == X**64 * X**32 * X**4
i.e.
X**100 == (((((X**2)**2)**2)**2)**2)**2 + ...
So what you do, is work out the powers of two of the total power you want to reach, and then take the product of those powers of two of the Q matrix.
This seems to work for me:
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]
And then, you can take it a step even further - it's just a 2x2 matrix, so we can diagonalise it, and then get the formula for the nth fibonacci number, just as a function of n - with no recursion. Like this:
As above, we compute the matrix that takes us from one step to the next:
And then the relationship to get from one set of numbers to the next:
where we can chain these matrix multiplications:
Where there's nothing to stop us going back all the way to the first fibonacci numbers:
now the game becomes "how do we raise that matrix to the power n" - which is exactly what's done in the code above. But there is a better way than the solution i pose above. We can decompose the Q-matrix into eigen values and vectors, a write it like so:
Where U is a unitary matricies that contain the eigen values of Q, and Λ is the matrix of corersponding eigenvalues. These eigenvalues and vecors are:
And then you use one of the standard advantages of this style of decomposition, where when you raise it to a power, the adjacent U matrix and it's inverse combine to give the unitary matrix, leaving you with a single U and it's inverse at the ends, with a chain of diagonal matrices in the middle, where raising these to a power is trivial:
So now we have all we need to write the nth Fibonacci number in terms of just a single formula, no recursion. I'll complete it tomorrow/some time later this week though...
这篇关于n的第N个斐波那契数等于10 ^ 19？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
