c++ - 巨大的斐波那契模 m C++

Question

我正在尝试计算 Fn mod m，其中 Fn 是第 n 个斐波那契数。 n 可能真的很大，所以以直接的方式计算 Fn 确实效率不高(尽管矩阵求幂会有效)。问题陈述要求我们在不计算 Fn 的情况下执行此操作，使用模的分配属性:(a+b)mod m = [a mod m + b mod m] mod m

(在有人问我之前，我查找了同一个问题的答案。但是，我想要我的特定问题的答案，因为我不是在询问解决此问题的算法问题)

利用这一点以及第 n 个斐波那契数只是前两个数之和这一事实，我不需要存储斐波那契数，而只需存储连续模运算的计算结果。从这个意义上讲，我应该有一个大小为 n 的数组 F，其中存储了使用上述属性迭代计算 Fn mod m 的结果。我已经设法使用以下代码解决了这个问题。然而，在查看它时，我偶然发现了一些让我很困惑的事情。

long long get_fibonacci_huge_mod(long long n, long long m) {

    long long Fib[3] = {0, 1, 1};
    long long result;
    long long index;
    long long period;
    long long F[n+1];
    F[0] = 0;
    F[1] = 1;
    F[2] = 1;

    for (long long i = 3; i <= n; i++) {
      F[i] = (F[i-2] + F[i-1]) % m;
      if (F[i] == 0 && F[i+1] == 1 && F[i+2] == 1) {
        period = i;
        break;
      }
    }


    index = n % period;
    result = F[index];
    return result;

}

此解决方案为任何 n 和 m 输出正确的结果，即使它们非常大。当 n 很大时它可能会有点慢，但我现在并不担心。我有兴趣以这种方式专门解决问题。 稍后，我将尝试使用矩阵求幂或任何其他更快的算法来解决它。

所以我的问题如下。在代码的开头，我创建了一个大小为 n+1 的数组 F。然后我遍历这个数组，使用分配属性计算 Fn mod m。写完这个循环后让我感到困惑的一件事是，由于 F 被初始化为全零，它如何正确使用 F[i+2]、F[i+1]，如果它们没有被初始化计算出来了吗？我假设它们被正确使用，因为算法每次都输出正确结果。也许这个假设是错误的？

我的问题与算法本身无关，我想问的是循环内部发生了什么。

谢谢

Answer 1

这是正确算法的错误实现。让我们先看看更正后的版本。

long long get_fibonacci_huge_mod(long long n, long long m) {
    long long result;
    long long index;
    long long period = n+1;
    long long sz = min (n+1,m*m+1); // Bound for period
    long long *F = new long long[sz];
    F[0] = 0;
    F[1] = 1;
    F[2] = 1;

    for (long long i = 3; i < sz; i++) {
      F[i] = (F[i-2] + F[i-1]) % m;
      if (F[i] == 1 && F[i-1] == 0) { // we have got back to where we started
        period = i-1;
        break;
      }
    }

    index = n % period;
    result = F[index];
    delete[]F;
    return result;

}

那么为什么原始代码可以工作？因为你走运了。由于数组被初始化为幸运垃圾，对 i+1 和 i+2 的检查从未评估为真。结果，这减少了对 F(n) 的简单评估，根本没有包含周期性。