java - 更快的算法来找到斐波那契 n mod m

Question

我用了将近 3 天的时间撞墙寻找一种快速算法来找到 fib n mod m，即斐波那契数 n 除以 m 的余数，其中:1 <= n < = 10^18 和 2 <= m <= 10^5

举个例子，我给出的是:

Input: 281621358815590 30524 // n and m
Output: 11963

通过这个测试，我的代码可以工作，但是测试失败了:100 100000

这是我的代码:

import java.math.BigInteger;
import java.util.Scanner;

public class FibonacciHuge {
    private static BigInteger fibmod(long n, BigInteger m) {
        BigInteger a=BigInteger.ZERO;
        BigInteger b=BigInteger.ONE;
        BigInteger c;
        long i;
        for (i=2; i<=n;i++){
            c=a.add(b);
            a=b;
            b=c;
        }
        return b.mod(m);
      }

    private static BigInteger fibComplex (long n, BigInteger m) {
        int count = 2;
        for (int i = 2; i < (m.pow(2)).longValue()-1; i++) {
            long a2=fibmod(i+1,m).longValueExact();
            long a3=fibmod(i+2,m).longValueExact();
            count= count+1;
            if (a2==0 && a3==1){
                break;
            }

        }   
        return fibmod(n % count,m);
    }

      public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        BigInteger m = in.nextBigInteger();
        System.out.println(fibComplex(n,m));
        in.close();
      }
}

在 fibmod() 中，我找到了 n 的斐波那契数列，最后我使用 m 作为调制器。在 fibComplex() 中，我想找到 Pisani 周期的长度，所以我使用 reduce n 到 n % (lengthofPisaniPeriod) 的余数，然后应用mod m(所以 n 不是那么大)。对于 Java，这应该在 1.5 秒内完成，但对于大的 Pisani 周期(如 100,000)，它就太多了。有 friend 说他们没有先找到 Fib n 就做了，只是迭代找到周期的长度并使用提示将 n 减少到 n % (length of period) 的余数。

我搜索了最快的斐波那契算法 here但解决方案似乎更容易，如我之前所述，关于减少 n，但我可以在 3 天后掌握这个概念。我正在使用 BigIntegers 但我不确定它是否真的需要，因为提示说:

"In this problem, the given number n may be really huge. Hence an algorithm looping for n iterations will not fit into one second for sure. Therefore we need to avoid such a loop".

您可以找到皮萨尼周期/周期计算器 here ，即使对于大量数据，它也能快速工作，所以我希望我能知道他们使用什么算法。

抱歉，如果我的问题中有什么地方不清楚，现在是上午 11 点，我整晚都没睡，试图解决这个问题。如果需要，我可以编辑它，让它在睡几个小时后更清晰。

Answer 1

您使用的动态方法不够快。您可以尝试矩阵求幂，或者更好的是，快速加倍。这个想法是给定 F(k) 和 F(k+1)，我们可以计算这些:

F(2k) = F(k) [2F(k+1) − F(k)]
F(2k+1) = F(k+1)^2 + F(k)^2

在 Java 中它会是这样的:

private static BigInteger fastFibonacciDoubling(int n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        int m = 0;
        for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
            // Loop invariant: a = F(m), b = F(m+1)

            // Double it
            BigInteger d = multiply(a, b.shiftLeft(1).subtract(a));
            BigInteger e = multiply(a, a).add(multiply(b, b));
            a = d;
            b = e;
            m *= 2;

            if (((n >>> i) & 1) != 0) {
                BigInteger c = a.add(b);
                a = b;
                b = c;
                m++;
            }
        }
        return a;
    }

应用此方法而不是您在答案中插入的方法，您会看到不同之处。 ;)

您可以在 https://www.nayuki.io/page/fast-fibonacci-algorithms 找到更多关于不同斐波那契方法的比较。 .