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

Question

目标是计算F（n）模m（m等于10的幂5），其中n可能真的很大：最多10的幂18。

我的算法太慢了。

我的方法：计算并存储所有不超过m的斐波那契数，然后遍历该数组并对斐波那契数取模。

一旦找到pisano周期的长度，我就可以使用该长度来计算任何 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大大提高...乘数/加法器的比例位宽，并且恒定时间也要好得多...

IIRC还有快速斐波那契计算的公式（转换O(N)为近似值）O(log(N))

这里有几个例子：快速斐波那契算法

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

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

注意要遵守您的约束，所使用的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

但是正如您所看到的，您早在那之前就已经染上了老年...