Modulus with negative numbers in C++
Solution 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; }
Solution 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 secondsWith
?
: 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.
Solution 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
.
Solution 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; }
Solution 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).
nitish712
Algorithms Enthusiast. When I'm Idle, you will find me doing some random experiments on a Linux Box or playing with some new feature in Java.
Updated on August 22, 2022Comments
-
nitish712 over 1 year
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 theModulus