Modulus with negative numbers in C++ [duplicate]

Question

I have been writing a program for the following recurrence relation:

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

The output should be the Answer modulus 10^9 + 7.. I wrote a brute force approach for this one as follows...

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);

where MOD= 10^9 +7 Every thing seems to be true.. but i am getting negative answer for some values.. and due to this problem, I am unable to find the correct solution... Plz help about the right place to keep the Modulus

Barby

Shouldn't you use unsigned long long for sum? – Belt

@Belt it wouldn't make any difference if the % operator always returned a positive value, but since it sometimes gives a negative result, signed variables should be used. – Dermatoid

@Hurkyl- you're right. Comment removed. – Bechuana

Does either ANSI C or ISO C specify what -5 % 10 should be?, Modulo operation with negative numbers, Why is the behavior of the modulo operator (%) different between C and Ruby for negative integers? – Ziguard

Answer 1

The thing is that the % operator isn't the "modulo operator" but the "division remainder" operator with the following equality

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

So, if in case your integer division rounds towards zero (which is mandated since C99 and C++11, I think), -5/4 will be -1 and we have

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

In order to get a positive result (for the modulo operation) you need to add the divisor in case the remainder was negative or do something like this:

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

Zwiebel

Answer 2

Using % a second time in @sellibitze's and @liquidblueocean's answers probably won't be as slow as % tends to be in general, because it boils down to either one subtraction of b or none. Actually, let me just check that...

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;
}

Alternatively commenting the line with % or the other line, we get:

• With %: 14 seconds

• With ?: 7 seconds

So % is not as optimised as I suspected. Probably because that optimisation would add overhead.

Therefore, it's better to not use % twice, for performance reasons.

Instead, as this answer suggests and explains, do this:

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

It takes a bit more work if you want it to work properly for negative n too, but that's almost never necessary.

Feathery

Answer 3

Just replace % by a function that handles negative values:

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: Changed the data type to long long int.

Narcosis

Answer 4

All answers currently here that have a once-off addition in their formula are wrong when abs(a) > b. Use this or similar:

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

Frei

Answer 5

As others have said % is just a remainder operator rather than mod. However, the mod/remainder operation distributes correctly through recurrence relations like this, so if you just adjust your final solution to be positive, like this,

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

then you should get the right answer. The advantage of doing it this way is that you introduce one less function call and/or branch per loop iteration. (Which may or may not matter depending on how clever your compiler is).

Bechuana

Note you can solve this in O(log(N)) time if you use modular matrix exponentiation rather than using the recurrence relation directly (which is O(N)). – Bechuana