Mod of negative number is melting my brain

Question

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 :(

Answer 1

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.

Answer 2

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.

Answer 3

Single-line implementation using % only once:

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

Answer 4

Comparing top two 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.

Answer 5

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

Answer 6

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.

Answer 7

Just add your modulus (arrayLength) to the negative result of % and you'll be fine.

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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)

Answer 12

There are many implementations of the mod function, and I think it's worth it to list all of them --- at least according to Wikipedia, I'm sure there are more.

// Important to be able to use `MathF`.
using System;

public static class MathFUtils {
    public static class Mod {
        public static float Trunc(float a, float b) =>
            a - b * ((int)(a / b));

        public static float Round(float a, float b) =>
            a - b * MathF.Round(a / b);

        public static float Floor(float a, float b) =>
            a - b * MathF.Floor(a / b);

        public static float Ceil(float a, float b) =>
            a - b * MathF.Ceiling(a / b);

        public static float Euclidean(float a, float b) =>
            a - MathF.Abs(b) * MathF.Floor(a / MathF.Abs(b));
    }
}

---

According to the Wikipedia (as well as my experience) stick to Euclidean. It is the most useful in terms of mathematical and probabilistic properties. If you ever need Trunc, then I believe % does just that.

Also, for those of you who might be confused as to what each of them do, and how, I highly recommend reading the Wikipedia article (even if it's hard) and looking at the images of each representation.

Of course these are not necessarily the most performant, but they do work. If you are concerned about performance, I recommend finding a local C# god, or asking one as they pass through our mortal plane.

Answer 13

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

Answer 14

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;

Answer 15

ShreevatsaR's second answer:

int mod(int x, int m) {
    int r = x % m;
    return r < 0 ? r + m : r;
}

can be written using the var pattern and switch expressions in newer versions of C# as a one-liner:

int mod(int x, int m) => (x % m) switch 
{ 
    < 0 and var r => r + m, var r => r 
}