以模爲單位的小錯誤

Question

我寫了一個計算一系列數字的小算法，但最終他們得到一個大的存儲在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; 
} 

這將返回一個向量，其具有一系列數字：

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內計算。

Answer 1

你可以檢查你的彈性模量是否足夠小。你有沒有在你的系統上檢查一個無符號long long的大小？

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

當你檢查，你不妨也同時檢查一個unsigned int 的大小。我不確定它們有什麼不同。

您的模數有10位數字，所以兩個數字的乘積可以有20位數字。如果您的最大無符號長整型長度小於MOD * MOD，則可能會出現溢出錯誤。

公式中的錯誤可能會在n = 51之前出現。

評論： 如果您使用的是C++ 11的標準，爲什麼不

constexpr unsigned long long MOD = 1000000007; 

而且替換宏，在調用modpow現場，你能避免所有這些類型轉換unsigned long long通過只需調用您想要的特定功能： modpow<unsigned long long>。然後參數將自動轉換爲正確的類型。