c++ - 取模时的小误差

我写了一个小算法来计算一系列数字，但是最终它们变得很大以存储在unsigned long long中。这就是为什么我决定在每次计算下一个数字时取模。这是我的功能:

#define MOD 1000000007

template <typename T>
T modpow(T base, T exp, T modulus) {
    base %= modulus;
    T result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}

vector<unsigned long long> B(int n) {
    vector<unsigned long long> points;
    vector<unsigned long long> cum_points;

    points.push_back(0);
    points.push_back(0);

    cum_points = points;

    unsigned long long prev = 0;
    if (n >= 2){
        for (int i = 0; i <= n - 2; i++) {
            prev += cum_points[i];
            prev %= MOD;
            points.push_back((modpow((unsigned long long)2, (unsigned long long)i, (unsigned long long) MOD)+prev)%MOD);
            cum_points.push_back((cum_points[i+1]+points[i+2])%MOD);
        }
    }
    return points;
}

这将返回带有一系列数字的 vector :

0，
0，
1，
2，
5
12
28，
64，
144，
320，
704，
1536，
3328，
...

等等...

问题是，当n > 50时，模数略有偏离:
(第一个值是在代码中不带模的情况下计算的值，等号后的值是代码中带模的结果。)

50: 1759218604441600 % 1000000007 = 592127074; this is the right answer
51: 3588805953060860 % 1000000007 = 927939229; this should be: 927939225

每当n变高时，错误就会变大。这个小额补偿来自何处？

一些可能的问题:

当数字时modpow()不能正确给出答案
超过一定长度。 这不是问题

数学上有一些错误，但是我相信我以正确的方式使用了以下方程式:

(a*b) mod c = ((a mod c)*(b mod c)) mod c(a + b) mod c = ((a mod c)+(b mod c)) mod c

我也可能在代码中使用错误的变量类型，尽管我不知道在哪里。

编辑:我已经排除了一些可能的问题，而问题似乎在于prev时在i == 48的计算中。

最佳答案

您可以检查模数是否足够小。您是否检查过系统中unsigned long long的大小？

std::cout << std::numeric_limits<unsigned long long>::max();

当您检查时，还可以检查未签名的int的大小
同时。我不确定它们是否一定有所不同。

您的模数有10位数字，所以两个数字的乘积最多可以有20位数字。如果max unsigned long long小于MOD * MOD，则可能会出现溢出错误。

公式中的错误可能在n = 51之前出现。

评论:
如果您使用的是C++ 11标准，为什么不将该宏替换为

constexpr unsigned long long MOD = 1000000007;

另外，在调用modpow的位置，只需调用所需的特定函数，就可以避免将所有这些类型强制转换为unsigned long long:modpow<unsigned long long>。然后，参数将自动转换为正确的类型。

关于c++ - 取模时的小误差，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29907554/