I'm trying to mod an integer to get an array position so that it will loop round. Doing i %
arrayLength
works fine for positive numbers but for negative numbers it all goes wrong.
4 % 3 == 1
3 % 3 == 0
2 % 3 == 2
1 % 3 == 1
0 % 3 == 0
-1 % 3 == -1
-2 % 3 == -2
-3 % 3 == 0
-4 % 3 == -1
so i need an implementation of
int GetArrayIndex(int i, int arrayLength)
such that
GetArrayIndex( 4, 3) == 1
GetArrayIndex( 3, 3) == 0
GetArrayIndex( 2, 3) == 2
GetArrayIndex( 1, 3) == 1
GetArrayIndex( 0, 3) == 0
GetArrayIndex(-1, 3) == 2
GetArrayIndex(-2, 3) == 1
GetArrayIndex(-3, 3) == 0
GetArrayIndex(-4, 3) == 2
I've done this before but for some reason it's melting my brain today :(
Please note that C# and C++'s % operator is actually NOT a modulo, it's remainder. The formula for modulo that you want, in your case, is:
float nfmod(float a,float b)
{
return a - b * floor(a / b);
}
You have to recode this in C# (or C++) but this is the way you get modulo and not a remainder.
Here's my one liner for positive integers, based on this answer:
usage:
(-7).Mod(3); // returns 2
implementation:
static int Mod(this int a, int n) => (((a %= n) < 0) ? n : 0) + a;
For the more performance aware devs
uint wrap(int k, int n) ((uint)k)%n
A small performance comparison
Modulo: 00:00:07.2661827 ((n%x)+x)%x)
Cast: 00:00:03.2202334 ((uint)k)%n
If: 00:00:13.5378989 ((k %= n) < 0) ? k+n : k
As for performance cost of cast to uint have a look here
Just add your modulus (arrayLength) to the negative result of % and you'll be fine.
ShreevatsaR's answer won't work for all cases, even if you add "if(m<0) m=-m;", if you account for negative dividends/divisors.
For example, -12 mod -10 will be 8, and it should be -2.
The following implementation will work for both positive and negative dividends / divisors and complies with other implementations (namely, Java, Python, Ruby, Scala, Scheme, Javascript and Google's Calculator):
internal static class IntExtensions
{
internal static int Mod(this int a, int n)
{
if (n == 0)
throw new ArgumentOutOfRangeException("n", "(a mod 0) is undefined.");
//puts a in the [-n+1, n-1] range using the remainder operator
int remainder = a%n;
//if the remainder is less than zero, add n to put it in the [0, n-1] range if n is positive
//if the remainder is greater than zero, add n to put it in the [n-1, 0] range if n is negative
if ((n > 0 && remainder < 0) ||
(n < 0 && remainder > 0))
return remainder + n;
return remainder;
}
}
Test suite using xUnit:
[Theory]
[PropertyData("GetTestData")]
public void Mod_ReturnsCorrectModulo(int dividend, int divisor, int expectedMod)
{
Assert.Equal(expectedMod, dividend.Mod(divisor));
}
[Fact]
public void Mod_ThrowsException_IfDivisorIsZero()
{
Assert.Throws<ArgumentOutOfRangeException>(() => 1.Mod(0));
}
public static IEnumerable<object[]> GetTestData
{
get
{
yield return new object[] {1, 1, 0};
yield return new object[] {0, 1, 0};
yield return new object[] {2, 10, 2};
yield return new object[] {12, 10, 2};
yield return new object[] {22, 10, 2};
yield return new object[] {-2, 10, 8};
yield return new object[] {-12, 10, 8};
yield return new object[] {-22, 10, 8};
yield return new object[] { 2, -10, -8 };
yield return new object[] { 12, -10, -8 };
yield return new object[] { 22, -10, -8 };
yield return new object[] { -2, -10, -2 };
yield return new object[] { -12, -10, -2 };
yield return new object[] { -22, -10, -2 };
}
}
You're expecting a behaviour that is contrary to the documented behaviour of the % operator in c# - possibly because you're expecting it to work in a way that it works in another language you are more used to. The documentation on c# states (emphasis mine):
For the operands of integer types, the result of a % b is the value produced by a - (a / b) * b. The sign of the non-zero remainder is the same as that of the left-hand operand
The value you want can be calculated with one extra step:
int GetArrayIndex(int i, int arrayLength){
int mod = i % arrayLength;
return (mod>=0) : mod ? mod + arrayLength;
}
Single-line implementation using %
only once:
int mod(int k, int n) { return ((k %= n) < 0) ? k+n : k; }
I like the trick presented by Peter N Lewis on this thread: "If n has a limited range, then you can get the result you want simply by adding a known constant multiple of [the divisor] that is greater that the absolute value of the minimum."
So if I have a value d that is in degrees and I want to take
d % 180f
and I want to avoid the problems if d is negative, then instead I just do this:
(d + 720f) % 180f
This assumes that although d may be negative, it is known that it will never be more negative than -720.
Comparing two predominant answers
(x%m + m)%m;
and
int r = x%m;
return r<0 ? r+m : r;
Nobody actually mentioned the fact that the first one may throw an OverflowException
while the second one won't. Even worse, with default unchecked context, the first answer may return the wrong answer (see mod(int.MaxValue - 1, int.MaxValue)
for example). So the second answer not only seems to be faster, but also more correct.
All of the answers here work great if your divisor is positive, but it's not quite complete. Here is my implementation which always returns on a range of [0, b)
, such that the sign of the output is the same as the sign of the divisor, allowing for negative divisors as the endpoint for the output range.
PosMod(5, 3)
returns 2
PosMod(-5, 3)
returns 1
PosMod(5, -3)
returns -1
PosMod(-5, -3)
returns -2
/// <summary>
/// Performs a canonical Modulus operation, where the output is on the range [0, b).
/// </summary>
public static real_t PosMod(real_t a, real_t b)
{
real_t c = a % b;
if ((c < 0 && b > 0) || (c > 0 && b < 0))
{
c += b;
}
return c;
}
(where real_t
can be any number type)
I always use my own mod
function, defined as
int mod(int x, int m) {
return (x%m + m)%m;
}
Of course, if you're bothered about having two calls to the modulus operation, you could write it as
int mod(int x, int m) {
int r = x%m;
return r<0 ? r+m : r;
}
or variants thereof.
The reason it works is that "x%m" is always in the range [-m+1, m-1]. So if at all it is negative, adding m to it will put it in the positive range without changing its value modulo m.
Adding some understanding.
By Euclidean definition the mod result must be always positive.
Ex:
int n = 5;
int x = -3;
int mod(int n, int x)
{
return ((n%x)+x)%x;
}
Output:
-1
A single line implementation of dcastro's answer (the most compliant with other languages):
int Mod(int a, int n)
{
return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
}
If you'd like to keep the use of %
operator (you can't overload native operators in C#):
public class IntM
{
private int _value;
private IntM(int value)
{
_value = value;
}
private static int Mod(int a, int n)
{
return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
}
public static implicit operator int(IntM i) => i._value;
public static implicit operator IntM(int i) => new IntM(i);
public static int operator %(IntM a, int n) => Mod(a, n);
public static int operator %(int a, IntM n) => Mod(a, n);
}
Use case, both works:
int r = (IntM)a % n;
// Or
int r = a % n(IntM);
Source: Stackoverflow.com