替代长,以避免溢出斐波纳契数

Question

Stackoverflow的新功能所以请指出我可以做的任何事情来提高我的问题的质量.

所以我的代码做(或者说希望做)什么是计算巨大的斐波那契数模相当庞大米.为了使算法更有效,我使用了pisano时期.本质上,我计算m的pisano周期,然后使用以下关系更容易计算余数:

的所述的剩余部分Ñ个Fibonacci数(模米)等于所述的剩余ķ个Fibonacci数(模米),使得ķ = ñ%p,其中p是的皮萨诺期间米.

为了计算pisano时期,我使用以下属性:

如果当前的Fib%米 = 0,并且所有的FIB的总和直到现在%米 = 0,则当前的Fib的索引为的皮萨诺期间米.(注意索引必须大于0)

然而,我在这方面遇到了一个问题:为了计算pisano时期,我必须计算连续的Fibonacci数.当必须计算的斐波纳契数的数量变得非常大时,例如100 000,就会出现问题.然后数据类型长溢出.

据我所知,任何计算皮萨诺时期的努力都需要计算斐波那契,所以唯一的解决方案似乎是用其他东西替换长期.如果有人对这个替代品有什么建议,我将不胜感激.

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,但要注意它会慢得多,但是尺寸无限大.