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

Question

我用了快3天的时间撞墙找了一个快速算法求fib nmodm，也就是斐波那契数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 作为 mod 计算器。在 fibComplex() 中，我想找到 Pisani 周期的长度，所以我使用 reduce n 到 n % (lengthofPisaniPeriod) 的余数，然后应用 mod m（所以 n 不是很大）。对于 Java，这应该在 1.5 秒内完成，但对于大的 Pisani 周期（如 100,000），它就太多了。有朋友说没有先求Fib n就做了，只是迭代求周期的长度，用tip把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".

您可以找到一个 Pisani cycle/period 计算器 here，即使对于大数，它也能快速工作，所以我希望我能知道他们使用什么算法。

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

Answer 1

诀窍是在计算时防止位数增长太大。让我们return进行第一个程序。这是一个数学事实：(a + b) mod M == ((a mod M) + (b mod M)) .因此：改变程序计算'c'modM；那么最后你只需要直接return 'b'。

我知道每次迭代计算 mod M 似乎很昂贵，但它不会像看起来那么糟糕，因为 'a' 和 'b' 保持小于 M。在事实上，如果你这样做，你甚至不需要使用 'mod()' 函数：'a' 和 'b' 在整个循环中都在 M 之下，因此 [=19= 的下一个值] 会小于2M；您只需要检查它是否超过 M，如果是，减去 M -一次-。事实上，我会为 'c' 编写如下代码（当然是概念上的；您需要使用 BigNum 方法）：

    c = a + b;
    c1 = c - M;   // need to declare c1
    if ( !c1.negative() ) c = c1;

[我这样做是因为 'c >= M' 和 'c = c - M' 几乎是相同的操作，所以为什么要承担两次成本？当然，我还假设 BigNum 有一个比与零比较更快的符号测试方法。

Answer 2

这是通过22次测试的最终方案。它有点草率，可能可以重构，但有 2 小时的睡眠，我很高兴它起作用了。

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

public class FibonacciHugev2 {

    private static long lenP(BigInteger m) {
        long q=m.longValueExact();
        long a=0;
        long b=1;
        long c=0;
        long i;
        int count = 0;
        for (i=0; i<=(q*q)-1;i++){
            if (a==0 && b==1 && count > 0){
                break;
            }

            c=(a+b) % q;
            a=b % q;
            b=c % q;
            count = count + 1;  
        }
        return count;
      }

    private static BigInteger fibmod(long n, BigInteger m) {
        long r=n % lenP(m); 
        BigInteger a=BigInteger.ZERO;
        BigInteger b=BigInteger.ONE;
        BigInteger c;
        long i;
        if (r==0){
            return BigInteger.ZERO;
        }
        if (r==1){
            return BigInteger.ONE;
        }
        for (i=2; i<=r;i++){
            c=a.add(b);
            a=b;
            b=c;
        }
        return b.mod(m);
      }

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

Answer 3

您使用的动态方法不够快。您可以尝试矩阵求幂，或者更好的是，快速加倍。这个想法是，给定 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 找到更多关于不同斐波那契方法的比较。

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

Faster algorithm to find fibonacci n mod m

java

algorithm

fibonacci