我计算非常大的斐波那契数模的算法太慢

Question

目标是计算 F(n) 模 m（m 最大为 10 的 5 次方），其中 n 可能非常大：最大为 10 的 18 次方。我的算法太慢了。我的方法：计算并存储最多 m 的所有斐波那契数，然后迭代该数组并对斐波那契数应用模。一旦找到皮萨诺周期的长度，我可以使用这个长度来计算任何的模F(n)我的代码：import java.math.BigInteger;import java.util.*;public class FibonacciAgain {    private static ArrayList<BigInteger> calc_fib() {        ArrayList<BigInteger> fib = new ArrayList<>();        fib.add(BigInteger.ZERO);        fib.add(BigInteger.ONE);        for (int i = 2; i <= 100000; i++) {            fib.add(fib.get(i - 2).add(fib.get(i - 1)));        }        return fib;    }    private static long calculatePeriod(ArrayList<BigInteger> fib, long modulo) {        long periodLength = 0;        boolean periodFound = false;        long[] period = new long[1000000];        period[0] = 0;        period[1] = 1;        period[2] = 1;        int i = 3;        while (!periodFound) {            //period[i] = fib.get(i)            //period[i]= fib.get(i).divide(new BigInteger(String.valueOf(i))).longValue();            //System.out.println("Fib at " + i + ": " + fib.get(i));            period[i] = fib.get(i).mod(new BigInteger(String.valueOf(modulo))).longValue();            //System.out.println("1:" + period[i]);            //System.out.println("2:" + period[i - 1]);           // System.out.println("3: " + period[i - 2]);            if (i == 100000){                periodFound = true;                periodLength = i - 1;            }           // if (period[i] == 1 && period[i - 1] == 1 && period[i - 2] == 0) {            if (period[i - 1] == 1 && period[i - 2] == 0) {                periodFound = true;                periodLength = i - 2;                //System.out.println("found");            }            i++;        }        //System.out.println("Period Length:" + periodLength);        return periodLength;    }    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        long n = scanner.nextLong();        long m = scanner.nextLong();    }}有什么建议，如何让它更快？

Answer 1

没有必要使用，BigInteger因为：

1*2*3*4*...*N mod M
1+2+3+4+...+N mod M

是相同的

(...(((1*2 mod M)*3 mod M)*4 mod M)...*N mod M)
(...(((1+2 mod M)+3 mod M)+4 mod M)...+N mod M)

这应该会加速很多......从（假设的Karatsuba乘法）O(3*N*(n^log2(3)))和/或加法O(N*n) 到线性O(N)，其中n乘数/加法的位宽成比例，并且还有更好的恒定时间......

IIRC 那里还有快速斐波那契计算的公式（转换O(N)成接近的东西）O(log(N))

这里是朴素 ( ) 和快速（使用 2x2 矩阵平方的幂）算法的C++示例：modfib0modfib1

//---------------------------------------------------------------------------

int modfib0(int n,int m)

    {

    for (int i=0,x0=0,x1=1;;)

        {

        if (i>=n) return x1; x0+=x1; x0%=m; i++;

        if (i>=n) return x0; x1+=x0; x1%=m; i++;

        }

    }

//---------------------------------------------------------------------------

// matrix 2x2:  0 1

//              2 3

void modmul2x2(int *c,int *a,int *b,int m)  // c[4] = a[4]*b[4] %m

    {

    int t[4];

    t[0]=((a[0]*b[0])+(a[1]*b[2]))%m;

    t[1]=((a[0]*b[1])+(a[1]*b[3]))%m;

    t[2]=t[1]; // result is symetric so no need to compute: t[2]=((a[2]*b[0])+(a[3]*b[2]))%m;

    t[3]=((a[2]*b[1])+(a[3]*b[3]))%m;

    c[0]=t[0];

    c[1]=t[1];

    c[2]=t[2];

    c[3]=t[3];

    }

void modpow2x2(int *c,int *a,int n,int m)   // c[4] = a[4]^n %m

    {

    int t[4];

    t[0]=a[0]; c[0]=1;

    t[1]=a[1]; c[1]=0;

    t[2]=a[2]; c[2]=0;

    t[3]=a[3]; c[3]=1;

    for (;;)

        {

        if (int(n&1)!=0) modmul2x2(c,c,t,m);

        n>>=1; if (!n) break;

        modmul2x2(t,t,t,m);

        }

    }

int modfib1(int n,int m)

    {

    if (n<=0) return 0;

    int a[4]={1,1,1,0};

    modpow2x2(a,a,n,m);

    return a[0];

    }

//---------------------------------------------------------------------------

请注意，为了符合您的限制，所使用的int变量必须至少为 64 位宽！我在旧的 32 位环境中，不想用 bigint 类破坏代码，所以我只用这个进行测试：

int x,m=30000,n=0x7FFFFFFF;

x=modfib0(n,m);

x=modfib1(n,m);

结果如下：

[10725.614 ms] modfib0:17301 O(N)

[    0.002 ms] modfib1:17301 O(log2(N))

正如你所看到的，快速算法比线性算法快得多...但是对于 Windows 环境来说，测量的时间太短了，而且它的大部分时间很可能是开销而不是函数本身，所以我认为即使是它也应该足够快因为我估计n=10^18它的复杂性是：O(log2(N))

64-31 = 33 bits

0.002 ms * 33 = 0.066 ms

因此，64 位计算的执行时间应该远远低于0.1 ms我的机器（AMD A8-5500 3.2 GHz）上的执行时间，我认为这是可以接受的......

64 位的线性算法如下：

10.725614 s * 2^33 = 865226435999039488 s = 27.417*10^9 years

但正如你所看到的，你早在这之前就已经衰老了......

Answer 2

为了帮助加快速度，我修改了你的calculatePeriod()方法。我做了以下几件事。

1. 更改了要记忆的 fib 缓存。它是动态计算的并添加到列表中。如果您反复提示输入值，这会派上用场。那么就不需要重新计算缓存了。

2. 我还添加了一个映射来存储fibFirst斐波那契及其模数。

3. 我将您的 BigInteger 调用从 更改new BigInteger(String.valueOf(modulo))为BigInteger.valueOf(modulo)。不确定它是否更快，但更干净。

4. 最后，我移动了重新计算但在任何循环之外没有更改的值。

这是修改后的方法：

   static Map<Long, Map<Long,Long>> fibFirstMap = new HashMap<>();   

   static List<BigInteger> fibs = new ArrayList<>() {

      { 

      add(BigInteger.ZERO);

       add(BigInteger.ONE);

       add(BigInteger.ONE);

       add(BigInteger.TWO);

      }  

   };

   private static long calculateFirst(long nthfib, long modulo) {

      long fibFirst =

            fibFirstMap.computeIfAbsent(nthfib, k -> new HashMap<>()).getOrDefault(

                  modulo, -1L);

      if (fibFirst > 0L) {

         return fibFirst;

      }

      long periodLength = 0;

      boolean periodFound = false;

      long[] period = new long[1000000];

      period[0] = 0;

      period[1] = 1;

      period[2] = 1;

      int i = 3;

      BigInteger cons = BigInteger.valueOf(modulo);

      BigInteger nextFib;

      while (!periodFound) {

         if (i >= fibs.size()) {

            fibs.add(fibs.get(i - 2).add(fibs.get(i - 1)));

         }

         nextFib = fibs.get(i);

         period[i] = nextFib.mod(cons).longValue();

         if (i == 100000) {

            periodFound = true;

            periodLength = i - 1;

         }

         else if (period[i - 1] == 1 && period[i - 2] == 0) {

            periodFound = true;

            periodLength = i - 2;

         }

         i++;

      }

      fibFirst = nthfib % periodLength;

      fibFirstMap.get(nthfib).put(modulo, fibFirst);

      return fibFirst;

   }

更好的方法可能是研究摆脱BigInteger所建议的方法，并寻求基于数论进步的计算改进。