Небольшая ошибка при использовании modulo

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

• Я мог бы также иметь неправильный тип переменной в моем коде, хотя я не знал бы где.

EDIT: я исключил некоторые из возможных проблем, и проблема, кажется, лежит в расчете prev при i == 48.

Answer 1

Вы можете проверить, достаточно ли вашего модуля. Вы проверили размер 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>. Затем аргументы будут автоматически преобразованы в правильный тип.