3

N ie の非常に大きな値のフィボナッチを計算したい。O(logN) の複雑さで 10^6。これが私のコードですが、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;
}
4

2 に答える 2

7

次の繰り返しを使用します。

F 2 n −1 = F n 2 + F n −1 2

F 2 n = (2 F n −1 + F n ) F n

メモ化と一緒に。たとえば、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

これは、10 6番目のフィボナッチ数 (モジュロ 10 9 + 7) を数マイクロ秒で計算します。

>>> from timeit import timeit
>>> timeit(lambda:fibonacci_modulo(10 ** 6, 10 ** 9 + 7), number=1)
0.000083282997366
于 2013-02-08T22:35:04.907 に答える
4

real 0m2.335sコードを使用する時間は、まだ非常に遅いですが、より合理的です。

フィボナッチ数を計算するアルゴリズムは問題ありません（多少高速化できる微調整がいくつかありますが、それほど劇的なものはありません）。したがって、問題は、大きなBigIntegersでの操作が遅く、F(10^6)700,000ビット近くあることです。

剰余をモジュロで計算しmod = 10^9 + 7、に(mod-1)^2収まるようにするため、 sの代わりにsを使用して、各ステップで剰余を計算するlongことで、はるかに高速な実装を得ることができます。直接転写longBigInteger

public class FiboL {

    static final long mod = 1000000007L;

     static long fibo(long n){

          long F[][] = {{1,1},{1,0}};

          if(n == 0)
            return 0;
          power(F, n-1);
            return F[0][0]; //.mod(mod);
        }

    static void power(long F[][], long n){

          if( n == 0 || n == 1)
              return;
          long M[][] = {{1,1},{1,0}};

          power(F, n/2);
          multiply(F, F);

          if( n%2 != 0 )
             multiply(F, M);
        }

    static void multiply(long F[][], long M[][]){

          long x =  (F[0][0] * M[0][0]) % mod + (F[0][1] * M[1][0]) % mod;
          long y =  (F[0][0] * M[0][1]) % mod + (F[0][1] * M[1][1]) % mod;
          long z =  (F[1][0] * M[0][0]) % mod + (F[1][1] * M[1][0]) % mod;
          long w =  (F[1][0] * M[0][1]) % mod + (F[1][1] * M[1][1]) % mod;

          F[0][0] = x % mod;
          F[0][1] = y % mod;
          F[1][0] = z % mod;
          F[1][1] = w % mod;
    }
    public static void main(String[] args) {
        System.out.println(fibo(1000000));
    }
}

で実行されreal 0m0.083sます。

于 2013-02-08T21:49:54.273 に答える