Модуль с отрицательными номерами в С++

Я пишу программу для следующего рекуррентного отношения:

An = 5An-1 - 2An-2  - An-3 + An-4

Выход должен быть модулем ответа 10 ^ 9 + 7.. Я написал метод грубой силы для этого следующего:

long long int t1=5, t2=9, t3=11, t4=13, sum;
while(i--)
{
    sum=((5*t4) - 2*t3 - t2 +t1)%MOD;
    t1=t2;
    t2=t3;
    t3=t4;
    t4=sum;
}
printf("%lld\n", sum);

где MOD= 10^9 +7 Кажется, что все кажется правдой, но я получаю отрицательный ответ за некоторые ценности... и из-за этой проблемы я не могу найти правильное решение... Plz поможет найти подходящее место для хранения Modulus

Ответы

Ответ 1

Дело в том, что оператор% не является "модульным оператором", а оператором "деления остатка" со следующим равенством

(a/b)*b + a%b == a    (for b!=0)

Итак, если в случае, если ваше целочисленное деление округляется к нулю (что, как мне кажется, предусмотрено с C99 и С++ 11), -5/4 будет -1, и мы имеем

(-5/4)*4 + -5%4 == -5
  -1  *4    -1  == -5

Чтобы получить положительный результат (для операции с модулем), вам нужно добавить делитель, если остаток был отрицательным или сделать что-то вроде этого:

long mod(long a, long b)
{ return (a%b+b)%b; }

Ответ 2

Используя % второй раз в @sellibitze и @liquidblueocean ответы, вероятно, будут не такими медленными, как %, как правило, в целом, потому что он сводится к одному вычитанию b или none. Собственно, позвольте мне просто проверить, что...

int main(int argc, char **argv) {
    int a = argc;    //Various tricks to prevent the
    int b = 7;       //compiler from optimising things out.
    int c[10];       //Using g++ 4.8.1
    for (int i = 0; i < 1000111000; ++i)
        c[a % b] = 3;
        //c[a < b ? a : a-b] = 3;
    return a;
}

Альтернативно комментируя строку с помощью % или другой строки, мы получаем:

  • С %: 14 секунд

  • С ?: 7 секунд

Итак, % не так оптимизирован, как я подозревал. Вероятно, потому, что эта оптимизация добавит служебные данные.

Следовательно, лучше не использовать % дважды, по соображениям производительности.

Вместо этого, как этот ответ предлагает и объясняет, сделайте следующее:

int mod(int k, int n) {
    return ((k %= n) < 0) ? k+n : k;
}

Требуется немного больше работать, если вы хотите, чтобы он правильно работал для отрицательного n тоже, но это почти никогда не нужно.

Ответ 3

Просто замените % на функцию, которая обрабатывает отрицательные значения:

long long int mod(long long int a, long long int b) {
    long long int ret = a % b;
    if (ret < 0)
        ret += b;
    return ret;
}

EDIT: изменил тип данных на long long int.

Ответ 4

Все ответы на данный момент, которые имеют одноразовое дополнение в их формуле, ошибочны, когда abs (a) > b. Используйте это или подобное:

int modulo (int a, int b) { return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b; }

Ответ 5

Как говорили другие, % - это просто оператор остатка, а не mod. Тем не менее, операция mod/else распределяется правильно через такие повторяющиеся отношения, поэтому, если вы просто скорректируете свое окончательное решение как положительное, например,

if (sum < 0) { sum = sum + MOD; }

тогда вы должны получить правильный ответ. Преимущество этого заключается в том, что вы вводите один меньше вызовов функции и/или ветки на каждую итерацию цикла. (Что может или не может иметь значения в зависимости от того, насколько умный ваш компилятор).