フィボナッチn mod mを見つけるためのより速いアルゴリズム

Question

私はファイバーn mod mを見つけるために速いアルゴリズムを見つけるために壁に頭を当てています。フィボナッチ数nをmで割った余りはです。 ：、私のコードは動作し、この試験で

Input: 281621358815590 30524 // n and m 
Output: 11963 

：1 < = N = 10^18、例として2 < = M < = 10^5

<は、Iは以下のように与えられていテストは次のように失敗します。 100 100000

これは私のコードである：fibmod()で

import java.math.BigInteger; 
import java.util.Scanner; 

public class FibonacciHuge { 
    private static BigInteger fibmod(long n, BigInteger m) { 
     BigInteger a=BigInteger.ZERO; 
     BigInteger b=BigInteger.ONE; 
     BigInteger c; 
     long i; 
     for (i=2; i<=n;i++){ 
      c=a.add(b); 
      a=b; 
      b=c; 
     } 
     return b.mod(m); 
     } 

    private static BigInteger fibComplex (long n, BigInteger m) { 
     int count = 2; 
     for (int i = 2; i < (m.pow(2)).longValue()-1; i++) { 
      long a2=fibmod(i+1,m).longValueExact(); 
      long a3=fibmod(i+2,m).longValueExact(); 
      count= count+1; 
      if (a2==0 && a3==1){ 
       break; 
      } 

     } 
     return fibmod(n % count,m); 
    } 

     public static void main(String args[]) { 
     Scanner in = new Scanner(System.in); 
     long n = in.nextLong(); 
     BigInteger m = in.nextBigInteger(); 
     System.out.println(fibComplex(n,m)); 
     in.close(); 
     } 
} 

、Iはn個のフィボナッチを見つけ、最後に私は、変調器としてMを使用します。 fibComplex()では、私はピサニ期間の長さを見つけると仮定しているので、n % (lengthofPisaniPeriod)の残りにreduce nを使用して、mod mを適用します（nはそれほど大きくはありません）。 Javaの場合、これは1.5秒で実行する必要がありますが、Pisaniの大きなピリオド（100,000）ではあまりにも多すぎます。 友人の中には、最初にFib nを見つけずに、最後にピリオドの長さを見つけ、先端を使ってnをn % (length of period)の残りの部分に減らすことなくそれをしたと言った人もいます。

私は最も速いフィボナッチアルゴリズムhereを検索しましたが、解決方法は簡単です。前に説明したように、nを減らす方法は簡単ですが、3日後に概念を把握できます。私はのBigIntegerで働いているが、その本当に必要な場合は、ヒントが言うので、私は、わからない。この問題で

」

、与えられた数n個のn回の反復のためにループ本当に巨大したがって アルゴリズムであってもよいです。 については1秒に収まりませんので、このようなループを避ける必要があります。

hereピサニサイクル/ピリオド計算機を見つけることができます。大きな数字でも速く動作するので、どのアルゴリズムを使用しているかわかります。

申し訳ありません私の質問に何かが明確でない場合、それは午前11時と私はこれを解決しようと眠っていません。私はそれを編集することができますので、より明確に必要な場合は数時間の睡眠を取ることができます。

Answer 1

使用している動的方法が十分に速いわけではありません。 行列の累乗を試すこともできますし、より速く2倍にすることもできます。 考えられるのは、F（k）とF（k + 1）が与えられたとき、これらを計算することができるということです：

F（k）[2F（k + 1）-F（k）]
F（2K + 1）= F（K + 1）^ 2 + F（K）^ 2

Javaでは、このようなものであろう。この方法の代わりに、いずれかを適用

private static BigInteger fastFibonacciDoubling(int n) { 
     BigInteger a = BigInteger.ZERO; 
     BigInteger b = BigInteger.ONE; 
     int m = 0; 
     for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) { 
      // Loop invariant: a = F(m), b = F(m+1) 

      // Double it 
      BigInteger d = multiply(a, b.shiftLeft(1).subtract(a)); 
      BigInteger e = multiply(a, a).add(multiply(b, b)); 
      a = d; 
      b = e; 
      m *= 2; 

      if (((n >>> i) & 1) != 0) { 
       BigInteger c = a.add(b); 
       a = b; 
       b = c; 
       m++; 
      } 
     } 
     return a; 
    } 

あなたがあなたの答えに挿入した場合、あなたはその違いを見るでしょう。 ;）

異なったフィボナッチ法の比較については、https://www.nayuki.io/page/fast-fibonacci-algorithmsで見つけることができます。

Answer 2

トリックは、計算すると数字の桁数が大きくなりすぎないようにすることです。私たちは最初の手順に戻りましょう。これは数学的事実です：（a + b）mod M ==（（a mod M）+（b mod M））。したがって、 'c' mod Mを計算する手順を変更してください。最後に「b」を直接返す必要があります。

私は各反復で計算Mが高価だと知っていますが、 'a'と 'b'はMよりも小さいので、それほど悪くはありません。実際に、 'mod（）'関数を使う必要があります。 'a'と 'b'はループ全体を通してMの下にとどまるので、 'c'の次の値は2M未満になります。 Mを超えていないかどうかを確認する必要があります。もしそうなら、M-onceを減算するだけです。

c = a + b; 
    c1 = c - M; // need to declare c1 
    if (!c1.negative()) c = c1; 

「Cが> = M」ので、[私はそれをこのように実行します。（あなたはBIGNUMメソッドを使用する必要がありますもちろん、概念的には）次のように実際に、私は「C」のためのコードを記述しますと 'c = c - M'はフードの下ではほぼ同じ操作なので、なぜ2回コストがかかりますか？もちろん、私はBigNumがゼロとの比較よりも速いサインテスト方法を持っていると仮定しています。]

Answer 3

これは22回のテストに合格した最終的な解決策です。それはちょっとうんざりしていて、おそらくリファクタリングできるかもしれませんが、2時間の睡眠で、うまくいきました。

import java.math.BigInteger; 
import java.util.Scanner; 

public class FibonacciHugev2 { 

    private static long lenP(BigInteger m) { 
     long q=m.longValueExact(); 
     long a=0; 
     long b=1; 
     long c=0; 
     long i; 
     int count = 0; 
     for (i=0; i<=(q*q)-1;i++){ 
      if (a==0 && b==1 && count > 0){ 
       break; 
      } 

      c=(a+b) % q; 
      a=b % q; 
      b=c % q; 
      count = count + 1; 
     } 
     return count; 
     } 

    private static BigInteger fibmod(long n, BigInteger m) { 
     long r=n % lenP(m); 
     BigInteger a=BigInteger.ZERO; 
     BigInteger b=BigInteger.ONE; 
     BigInteger c; 
     long i; 
     if (r==0){ 
      return BigInteger.ZERO; 
     } 
     if (r==1){ 
      return BigInteger.ONE; 
     } 
     for (i=2; i<=r;i++){ 
      c=a.add(b); 
      a=b; 
      b=c; 
     } 
     return b.mod(m); 
     } 

     public static void main(String args[]) { 
     Scanner in = new Scanner(System.in); 
     long n = in.nextLong(); 
     BigInteger m = in.nextBigInteger(); 
     //System.out.println(lenP(m)); 
     System.out.println(fibmod(n,m)); 
     in.close(); 
     } 
    }