替代long以避免溢出斐波那契數字

Question

Stackoverflow的新功能，所以請指出任何我可以做的事情來提高我的問題的質量。

所以我的代碼做的（或者更確切地說希望做的）是計算巨大的斐波納契數字，以相當大的模數m。爲了使算法更有效率，我使用了pisano periods。從本質上說，我計算的米的皮薩諾週期，然後進行其餘的計算通過使用下面的關係更容易：

的的Ñ個斐波那契數（模米）的餘數是等於所述ķ個Fibonacci數（模米），使得ķ = ñ％p的其餘部分，其中p是皮薩諾時期米。

爲了計算Pisano的期間，我使用下面的屬性：

如果當前的Fib％米 = 0，並且所有的FIB的直到現在％的總和米 = 0 ，那麼當前Fib的指數是m的pisano期間。 （注意指數必須大於0）

但是我遇到了這個問題：爲了計算pisano時間，我必須計算連續的斐波納契數。當需要計算的斐波那契數量變得非常大時，例如100 000，這個問題就出現了。然後數據類型溢出。

據我所知，任何計算pisano時期的努力都需要計算斐波納契的時間，所以唯一的解決方案似乎是用其他東西替代long。如果有人對這個替代品有什麼建議，我將不勝感激。

import java.util.*; 

public class FibHuge { 
    public static void main (String [] args) { 
     Scanner in = new Scanner (System.in); 
     long num = in.nextLong(); 
     long mod = in.nextLong(); 

     System.out.println (getMod(num, mod)); 
    } 

    private static int getMod (long num, long mod) { 
     Period per = new Period(); 

     long period = per.getPeriod (mod); 
     int newFibNum = (int)(num % period); 

     num = (num % mod); 

     Integer ia[] = new Integer [per.al.size()]; 
     ia = per.al.toArray (ia); 

     return ia[newFibNum]; 
    } 
} 

class Period { 

    ArrayList <Long> al; 
    long FNum; 
    long SNum; 

    Period() { 
     al = new ArrayList <Long>(); 
     FNum = 0; 
     SNum = 1; 
    } 

    private long getFib (long first, long second){ 
     return first + second; 
    } 

    long getPeriod (long mod){ 
     boolean bool = true; 
     long fibcount = 0; 

     long currentmod = 0; 
     long fib = 0; 
     long sum = 0; 

     while (bool){ 
      if (fibcount <= 1){ 
       currentmod = fibcount % mod; 

       al.add (currentmod); 

       sum += fibcount; 
      } 

      else { 
       fib = getFib (FNum, SNum); 
       FNum = SNum; 
       SNum = fib; 

       currentmod = (fib % mod); 
       al.add (currentmod); 

       sum += fib; 
      } 

      if ((currentmod == 0 & (sum % mod) == 0) & fibcount > 0){ 
       return fibcount; 
      } 
      fibcount++; 
     } 

     return mod; //essentially just to satisfy the return condition 
    } 
} 

Answer 1

您不需要使用BigInteger，除非您的模數太大而不適合long，在這種情況下，我懷疑您會耗盡內存，試圖找到解決方案。

代替計算第n個斐波那契數，然後進行模數的，則可以使用該屬性

(a + b) % n = (a % n + b % n) % n; 

換句話說計算模數後的第n個斐波那契你只需要不斷增加的模量的數字在每次迭代中。您可以將所有模數值保存在Set中，並且當您得到重複的結果時，您有一段時間。您可以將迭代編號與結果一起存儲並使用它來計算週期。

事實上模量是一種昂貴的，但因爲你永遠只總結了一些小於2個*模量，你可以簡單地做

long c = a + b; // Fibonacci 
if (c >= modulus) c -= modulus; // the only real change you need for modulus. 

由於Java使用條件的舉動，而不是一個實際的分支這比使用更快%

我想不出更多的細節，你需要知道，而無需爲你編寫代碼。

Answer 2

使用BigInteger，但是請注意，這將是很慢，但具有無限的大小。