gpt4 book ai didi

algorithm - 大 N 值的矩阵求幂算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:04:17 24 4
gpt4 key购买 nike

我想计算非常大的 N 值的斐波那契,即。 10^6,复杂度为 O(logN)。这是我的代码,但它在 30 秒内给出了 10^6 的结果,这非常耗时。帮我指出错误。我必须以 10^9+7 为模给出输出。

static BigInteger mod=new BigInteger("1000000007");

BigInteger fibo(long n){
BigInteger F[][] = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
if(n == 0)
return BigInteger.ZERO;
power(F, n-1);
return F[0][0].mod(mod);
}

void power(BigInteger F[][], long n) {
if( n == 0 || n == 1)
return;
BigInteger M[][] = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
power(F, n/2);
multiply(F, F);
if( n%2 != 0 )
multiply(F, M);
}

void multiply(BigInteger F[][], BigInteger M[][]){
BigInteger x = (F[0][0].multiply(M[0][0])).add(F[0][1].multiply(M[1][0])) ;
BigInteger y = F[0][0].multiply(M[0][1]).add(F[0][1].multiply(M[1][1])) ;
BigInteger z = F[1][0].multiply(M[0][0]).add( F[1][1].multiply(M[1][0]));
BigInteger w = F[1][0].multiply(M[0][1]).add(F[1][1].multiply(M[1][1]));

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

最佳答案

使用这些 recurrences :

F2n−1 = Fn2 + Fn−12

F2n = (2Fn−1 + Fn) Fn

连同memoization .例如,在 Python 中,您可以使用 @functools.lru_cache装饰器,像这样:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
"""Compute the nth Fibonacci number modulo m."""
if n <= 3:
return (0, 1, 1, 2)[n] % m
elif n % 2 == 0:
a = fibonacci_modulo(n // 2 - 1, m)
b = fibonacci_modulo(n // 2, m)
return ((2 * a + b) * b) % m
else:
a = fibonacci_modulo(n // 2, m)
b = fibonacci_modulo(n // 2 + 1, m)
return (a * a + b * b) % m

这会在几微秒内计算第 106 斐波那契数(模 109 + 7):

>>> from timeit import timeit
>>> timeit(lambda:fibonacci_modulo(10 ** 6, 10 ** 9 + 7), number=1)
0.000083282997366

关于algorithm - 大 N 值的矩阵求幂算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14781543/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com