矩阵幂算法对于N大值 [英] Matrix Exponentiation Algorithm for large values of N

问题描述

我要计算N个即非常大的价值的斐波那契数。 10 ^ 6与O（logN）的复杂性。 这是我的code，但它给出结果为10 ^ 6 30秒，这是非常时期consuming.Help我指出了犯错误给输出模10 ^ 9 + 7。

 静态的BigInteger MOD =新的BigInteger（1000000007）;

BigInteger的FIBO（N久）{
    的BigInteger F [] [] = {{BigInteger.ONE，BigInteger.ONE}，{BigInteger.ONE，BigInteger.ZERO}};
    如果（N == 0）
        返回BigInteger.ZERO;
    功率（F，N-1）;
    返回F [0] [0]的.mod（MOD）;
}

无效功率（BigInteger的F [] []，N久）{
    如果（N == 0 ||ñ== 1）
        返回;
    的BigInteger M [] [] = {{BigInteger.ONE，BigInteger.ONE}，{BigInteger.ONE，BigInteger.ZERO}};
    功率（F，N / 2）;
    乘（F，F）;
    如果（正％2！= 0）
        乘（F，M）;
  }

无效乘法（BigInteger的F [] []，BigInteger的M [] []）{
    的BigInteger X =（F [0] [0] .multiply（M [0] [0]））添加（F [0] [1] .multiply（M [1] [0]））;
    的BigInteger Y = F [0] [0] .multiply（M [0] [1]）添加（F [0] [1] .multiply（M [1] [1]））;
    的BigInteger Z = F [1] [0] .multiply（M [0] [0]）添加（F [1] [1] .multiply（M [1] [0]））;
    的BigInteger瓦特= F [1] [0] .multiply（M [0] [1]）添加（F [1] [1] .multiply（M [1] [1]））;

    F [0] [0] = X;
    F [0] [1] = Y;
    F [1] [0] = Z;
    F [1] [1] =瓦特;
}
 

解决方案

使用这些复发：

  

F 的 _{2 N 1} = F 的<分> N ² + F 的<分> N 1 ²

     

F 的 _{2 N} =（2 F <分> N - 1 + F 的<分> N ）的 F 的<分> N

与记忆化。例如，在Python中，你可以使用 @memoized 从 Python的装饰库的这样的装饰：

@memoized 高清fibonacci_modulo（N，M）：     计算的第n个Fibonacci数模M     如果n＆其中; = 3：         返回（0，1，1，2）[n]的％间     ELIF N％2 == 0：         A = fibonacci_modulo（N // 2 - 1，M）         B = fibonacci_modulo（N // 2，M）         返回（（2 * A + B）* B）％间     其他：         A = fibonacci_modulo（N // 2，M）         B = fibonacci_modulo（正// 2 + 1，M）         回报（A * A + B * B）％M

该计算10 ⁶ 个Fibonacci数（模10 ⁹ + 7），在不到一毫秒：

 ＆GT;＆GT;＆GT;从timeit进口timeit
＆GT;＆GT;＆GT; timeit（拉姆达：fibonacci_modulo（10 ** 6，10 ** 9 + 7），数量= 1）
0.0004661083221435547
 

I want to calculate the Fibonacci of very large value of N ie. 10^6 with a complexity of O(logN). Here is my code but it gives the result for 10^6 in 30 seconds which is very time consuming.Help me point out the mistake.I have to give the output in modulo 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;
}

解决方案

Use these recurrences:

F_2n−1 = F_n² + F_n−1²

F_2n = (2F_n−1 + F_n) F_n

together with memoization. For example, in Python you could use the @memoized decorator from the Python Decorator Library like this:

@memoized
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

this computes the 10⁶th Fibonacci number (modulo 10⁹ + 7) in less than a millisecond:

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

这篇关于矩阵幂算法对于N大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！