巨大的斐波那契模数C ++ [英] Huge fibonacci modulo m C++

问题描述

我正在尝试计算Fn mod m，其中Fn是第n个斐波那契数。 n可能确实很大，因此以简单的方式计算Fn确实没有效率（但是矩阵求幂会起作用）。问题陈述要求我们使用模的分布特性，在不计算Fn的情况下执行 ：
（a + b）mod m = [a mod m + b mod m] mod m

I'm trying to calculate Fn mod m, where Fn is the nth Fibonacci number. n may be really huge, so its really not efficient to calculate Fn in a straightforward way (matrix exponentiation would work, though). The problem statement asks us to do this without calculating Fn, using the distributive property of the modulo: (a+b)mod m = [a mod m + b mod m] mod m

（在有人问我之前，我已经查找了相同问题的答案。但是，我想回答我的具体问题，因为我不是在问算法解决此问题）

(Before anyone asks me, I looked up answers to this same problem. I'd like an answer to my specific question, however, since I'm not asking about the algorithm to solve this problem)

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

Using this and the fact that the nth Fibonacci number is just the sum of the previous two, I don't need to store Fibonacci numbers, but rather only the results of calculating successive modulo operations. In that sense, I should have an array F of size n which has in it stored the results of iteratively calculating Fn mod m using the above property. I have managed to solve this problem using the following code. However, upon reviewing it, I stumbled upon something that rather confused me.

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很大时，它可能会变慢一些，但是我现在不担心这一点。我有兴趣以这种方式专门解决问题。我将尝试使用矩阵幂运算或任何其他更快的算法稍后解决它。

This solution outputs correct results for any n and m, even if they are quite large. It might get a little bit slow when n is huge, but I'm not worried about that right now. I'm interested in specifically solving the problem this way. I'll try solving it using matrix exponentiation or any other much faster algorithm later.

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

So my question is as follows. At the beginning of the code, I create an array F of size n+1. Then I iterate through this array calculating Fn mod m using the distributive property. One thing that confused me after writing this loop was the fact that, since F was initialized to all zeros, how is it correctly using F[i+2], F[i+1], if they haven't been calculated yet? I assume that they are being correctly used since the algorithm outputs correct results every time. Perhaps this assumption is wrong?

我的问题不是关于算法本身的问题，而是关于循环内 发生了什么。

My question isn't about the algorithm per se, I'm asking about what's going on inside the loop.

谢谢

推荐答案

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

This is a faulty implementation of a correct algorithm. Let us look at the corrected version first.

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的检查从未评估为true。结果，这简化为F（n）的天真评估而根本没有包含周期性。

So why does the original code work? Because you got lucky. The checks for i+1 and i+2 never evaluated to true because of the lucky garbage the array was initialized to. As a result this reduced to the naive evaluation of F(n) without incorporating periodicity at all.

这篇关于巨大的斐波那契模数C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！