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

Question

目标是计算 F(n) 模 m（m 的 10 次方 5），其中 n 可能非常大：最多 18 的 10 次方。

我的算法太慢了。

我的方法：计算并存储最大为 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();


        //M Fibonacci Numbers up to are stored here
        ArrayList<BigInteger> fib = new ArrayList<>();
        fib = calc_fib();

        // get the length of the pisano period
        long periodLength = calculatePeriod(fib, m);

        //
        long fibFirst = n%periodLength;
        System.out.println(fib.get((int) fibFirst).mod(new BigInteger(String.valueOf(m))).longValue());

    }
}

有什么建议，如何让它更快？

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 是成比例的位宽您的 multiplicants/additionals 也有更好的恒定时间 ...

IIRC 那里还有用于快速斐波那契计算的公式（将 O(N) 转换为接近 O(log(N))

的东西

这里举几个例子：fast fibonacci algorithms

此处 C++ 朴素 (modfib0) 和快速 (modfib1 通过 2x2 矩阵的平方使用幂) 算法的示例：

//---------------------------------------------------------------------------
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 class 破坏代码，所以我只测试了这个：

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 位计算应该在我的机器 (AMD A8-5500 3.2 GHz) 上的执行时间 0.1 ms 之下完成，我认为这是可以接受的...

64 位的线性算法是这样的：

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

但正如您所见，在那之前很久您就会老去...

Answer 2

为了加快速度，我修改了您的 calculatePeriod() 方法。我做了以下事情。

更改了要记忆的 fib 缓存。它是即时计算并添加到列表中的。如果您反复提示输入值，这会派上用场。那么就不需要重新计算缓存了。
我还添加了一个映射来存储 fibFirst 斐波那契及其模数。
我将您的 BigInteger 调用从 new BigInteger(String.valueOf(modulo)) 更改为 BigInteger.valueOf(modulo)。不确定它是否更快但更干净。
最后，我移动了重新计算但在任何循环之外都没有改变的值。

修改后的方法如下：

   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 所建议的方法，并根据数论的进步寻求改进计算。

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

My algorithm for calculating the modulo of a very large fibonacci number is too slow

java

algorithm

fibonacci