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

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