Alternative à long afin d'éviter débordement Numéros Fibonacci

Question

Nouveau à Stackoverflow alors s'il vous plaît signaler tout ce que je peux faire pour améliorer la qualité de ma question.

Donc ce que mon code fait (ou plutôt espère faire) est de calculer d'énormes nombres de fibonacci modulo un assez grand m. Pour rendre l'algorithme plus efficace, j'utilise l'utilisation de pisano periods. Essentiellement, je calculer la période Pisano de m et ensuite faire le calcul du reste plus facile à l'aide de la relation suivante:

Le reste de la n ième nombre de Fibonacci (modulo m) est égal au reste de la k ème nombre de Fibonacci (modulo m ) de telle sorte que k = n% de p où p est le période pisano de m.

Pour calculer la période Pisano, j'utilise la propriété suivante:

Si le FIB% courant m = 0 et la somme de tous Fib de jusqu'à maintenant% m = 0 , alors l'indice du fib actuel est la période pisano de m. (Notez que l'index doit être supérieur à 0)

Cependant, je rencontre un problème dans cette tentative: Pour calculer la période pisano, je dois calculer des nombres consécutifs de Fibonacci. Le problème se pose lorsque le nombre de nombres Fibonacci qui doivent être calculés devient très grand, disons 100 000. Ensuite, le type de données déborde longtemps. À ma connaissance, toute tentative de calculer des périodes pisano nécessitera le calcul de fibonacci, donc la seule solution semble être de remplacer longtemps par autre chose. Si quelqu'un a des suggestions quant à ce que ce remplacement pourrait être, je l'apprécierais grandement.

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

Vous n'avez pas besoin d'utiliser BigInteger à moins que votre module ne soit trop grand pour tenir dans un long auquel cas je suppose que vous manquerez de mémoire pour essayer de trouver la solution.

Au lieu de calculer le nombre de Fibonacci n-ième et en effectuant ensuite un module, vous pouvez calculer le n-ième Fibonacci après module utilisant cette propriété

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

En d'autres termes, il vous suffit de continuer à ajouter le module du nombre dans chaque itération. Vous pouvez enregistrer toutes les valeurs de module dans un ensemble et lorsque vous obtenez un résultat répété, vous avez un point. Vous pouvez stocker le numéro d'itération avec le résultat et l'utiliser pour calculer la période.

En module fait est un peu cher, mais puisque vous somme que jamais un nombre qui est inférieur à 2 module * vous pouvez simplement faire

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

Comme Java utilise un mouvement de condition plutôt qu'une branche réelle ce est beaucoup plus rapide que d'utiliser %

Je ne peux pas penser à beaucoup plus de détails que vous devez savoir sans écrire le code pour vous.

Answer 2

Utilisez BigInteger, mais prendre note que ce sera beaucoup plus lent, mais avec une taille infinie.