Modulus with negative numbers in C++

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

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

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.

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.

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

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