255

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

2

15 Answers 15

353

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.

25
  • 9
    Note: for complete number-theoretic completeness, you might want to add a line at the top saying "if(m<0) m=-m;" although in this case it doesn't matter as "arrayLength" is presumably always positive. Jul 4, 2009 at 20:47
  • 6
    If you are going to check the value of m, you should also exclude zero.
    – billpg
    Aug 25, 2009 at 9:52
  • 7
    @billpg: mod is not defined for m=0, so there's really nothing that the function can be expected to do for that case. IMHO, it's the caller's responsibility to check that. (No one should even want something mod 0.) OTOH, mod is defined for negative m, so I suggested fixing that bug in the code if the function may be called with negative m. Anyway, where error-checking/handling should be done is a perennial question :p Apr 2, 2012 at 5:49
  • 8
    @RuudLenders: No. If x = -5 and m = 2, then r = x%m is -1, after which r+m is 1. The while loop is not needed. The point is that (as I wrote in the answer), x%m is always strictly greater than -m, so you need to add m at most once to make it positive. Jan 25, 2013 at 14:15
  • 14
    +1. I don't care what any individual language does for a negative modulus - the 'least non-negative residue' exhibits a mathematical regularity and removes any ambiguity.
    – Brett Hale
    Jan 9, 2014 at 22:55
106

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.

10
  • 28
    "Please note that C++'s % operator is actually NOT a modulo, it's remainder. " Thanks, it makes sense now, always wonder why it never worked properly with negative numbers. Apr 1, 2012 at 23:36
  • 2
    "Please note that C++'s % operator is actually NOT a modulo, it's remainder. " I don't think this is accurate and I don't see why a modulo is any different from remainder. That's what it also says on the Modulo Operation Wikipedia page. It's just that programming languages treat negative numbers differently. The modulo operator in C# obviously counts remainders "from" zero (-9%4 = -1, because 4*-2 is -8 with a difference of -1) while another definition would consider -9%4 as +3, because -4*3 is -12, remainder +3 (such as in Google's search function, not sure of the back-end language there).
    – Tyress
    Aug 6, 2014 at 7:12
  • 24
    Tyress, there is a difference between modulus and remainder. For example: -21 mod 4 is 3 because -21 + 4 x 6 is 3. But -21 divided by 4 gives -5 with a remainder of -1. For positive values, there is no difference. So please inform yourself about these differences. And do not trust Wikipedia all the time :) Aug 6, 2014 at 8:50
  • 7
    Why would anyone want to use the remainder function instead of a modulo? Why did they make % remainder? Jan 26, 2018 at 22:20
  • 5
    @AaronFranke - its a legacy from earlier cpus that had division hardware to quickly produce a quotient and a remainder - and this is what that hardware did given a negative dividend. The language simply mirrored the hardware. Most of the time programmers were working with positive dividends, and ignored this quirk. Speed was paramount. Jan 23, 2019 at 22:45
23

Single-line implementation using % only once:

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }
4
  • 1
    is this correct? as I do not see it as accepted by anyone, nor any comments to it. For example. mod(-10,6) will return 6. Is that correct? should it not return 4? Feb 13, 2017 at 11:41
  • 4
    @JohnDemetriou Your numbers are both wrong: (A) it should return 2 and (B) it does return 2; try running the code. Item (A): to find mod(-10, 6) by hand, you either add or subtract 6 repetitively until the answer is in the range [0, 6). This notation means "inclusive on the left, and exclusive on the right". In our case, we add 6 twice, giving 2. The code is quite simple, and it's easy to see that it's right: first, it does the equivalent of adding/subtracting n as above, except that it stops one n short, if approaching from the negative side. In that case we fix it. There: comments :) Mar 20, 2017 at 1:03
  • 1
    By the way, here's a reason why using a single % might be a good idea. See the table What things cost in managed code in the article Writing Faster Managed Code: Know What Things Cost. Using % is similarly expensive to int div listed in the table: about 36 times more expensive than adding or subtracting, and about 13 times more expensive than multiplying. Of course, no big deal unless this is at the core of what your code is doing. Mar 20, 2017 at 1:16
  • 7
    But is a single % more expensive than a test and jump, especially if it can't easily be predicted?
    – Medinoc
    Oct 25, 2017 at 13:58
21

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.

7

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 };
        }
    }
8
  • 2
    Firstly, a mod function is usually called with positive modulus (note the variable arrayLength in the original question that is being answered here, which is presumably never negative), so the function doesn't really need to be made to work for negative modulus. (That is why I mention the treatment of negative modulus in a comment on my answer, not in the answer itself.) (contd...) Jan 5, 2014 at 3:52
  • 6
    (...contd) Secondly, what to do for a negative modulus is a matter of convention. See e.g. Wikipedia. "Usually, in number theory, the positive remainder is always chosen", and this is how I learnt it as well (in Burton's Elementary Number Theory). Knuth also defines it that way (specifically, r = a - b floor(a/b) is always positive). Even among computer systems, Pascal and Maple for instance, define it to be always positive. Jan 5, 2014 at 3:52
  • 1
    @ShreevatsaR I know that the Euclidian definition states that the result will always be positive - but I am under the impression that most modern mod implementations will return a value in the [n+1, 0] range for a negative divisor "n", which means that -12 mod -10 = -2. Ive looked into Google Calculator, Python, Ruby and Scala, and they all follow this convention.
    – dcastro
    Jan 7, 2014 at 1:22
  • 2
    Again, this is still a good read. The "always positive" definition (my answer) is consistent with ALGOL, Dart, Maple, Pascal, Z3, etc. The "sign of divisor" (this answer) is consistent with: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl, etc. Both are inconsistent with "sign of dividend" as in: AWK, bash, bc, C99, C++11, C#, D, Eiffel, Erlang, Go, Java, OCaml, PHP, Rust, Scala, Swift, VB, x86 assembly, etc. I really don't see how you can claim one convention is "correct" and others "wrong". Mar 23, 2017 at 18:02
  • 1
    BTW this answer currently claims to be consistent with "Java, Python, Ruby, Scala, Scheme, Javascript and Google's Calculator", but of those, it's actually not consistent with Java, Scala and Javascript -- try -12 mod 10, for which they all give -2, while this answer (and Python, Ruby, and Google's Calculator) gives 8. It's impossible to be simultaneously consistent both with Python and with Java/Javascript, as they are inconsistent with each other. Meanwhile, Sage has a mod which always returns a positive result: mod(-12, -10) == mod(-12, 10) == 8. Apr 24, 2019 at 0:18
5

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.

4
  • 2
    -1: not general enough, (and it is very easy to give a more general solution). Apr 22, 2014 at 7:32
  • 7
    This is actually very helpful. when you have meaningful range, this can simplify computation. in my case math.stackexchange.com/questions/2279751/… May 14, 2017 at 5:23
  • 1
    Exactly, just used this for dayOfWeek calculation (known range of -6 to +6) and it saved having two %.
    – NetMage
    Apr 10, 2019 at 17:57
  • 2
    @EvgeniSergeev +0 for me: doesn't answer OP question but can be helpful in a more specific context (but still in the context of the question)
    – Erdal G.
    Apr 30, 2020 at 12:36
4

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

0
4

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;
}
2
  • What does this add, that is not already covered by existing answers? Aug 3, 2021 at 14:03
  • 1
    @ToolmakerSteve for one thing it actually addresses the official language specification, which is the source of the misunderstanding on how % works, no other answer does that.
    – Andrew
    Aug 8, 2021 at 18:28
3

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

3
  • 4
    Methinks that -3 % 10 should either be -3 or 7. Since a non-negative result is wanted, 7 would be the answer. Your implementation returns 3. You should change both parameters to uint and remove the cast. Oct 5, 2015 at 13:55
  • 6
    Unsigned arithmetic is only equivalent if n is a power of two, in which case you can simply use a logical and ((uint)k & (n - 1)) instead, if the compiler doesn't already do it for you (compilers are often smart enough to figure this out).
    – j_schultz
    Apr 11, 2017 at 19:10
  • 1
    To summarize the above comments: This answer is wrong for negative k. It does not calculate the modulus. Don't use this answer. (My apologies for being blunt, but the upvotes are concerning. That suggests that some people have adopted an implementation that gives wrong answers.) Aug 4, 2021 at 21:11
3

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
3
  • 17
    I'm confused... you say that the result should always be positive, but then list the output as -1?
    – Jeff B
    Oct 2, 2015 at 21:42
  • @JeffBridgman I have stated that based on Euclidean definition. ` there are two possible choices for the remainder, one negative and the other positive, and there are also two possible choices for the quotient. Usually, in number theory, the positive remainder is always chosen, but programming languages choose depending on the language and the signs of a and/or n.[5] Standard Pascal and Algol68 give a positive remainder (or 0) even for negative divisors, and some programming languages, such as C90, leave it up to the implementation when either of n or a is negative.`
    – Abin
    Oct 5, 2015 at 15:19
  • Clarification: While useful, This isn't an "answer"; it is a comment on a limitation of another answer. Its a suggestion NOT to use certain answers; look at OTHER answers to see formulas that do work. [Nit-picking]: Also from your link: "In mathematics, the result of the modulo operation is an equivalence class, and any member of the class may be chosen as representative". So its a bit strong to say "the mod result must be positive"*. Despite the language earlier in that link. Aug 3, 2021 at 13:52
1

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)

3
  • How is this different than dcastro's answer? Aug 3, 2021 at 14:02
  • @ToolmakerSteve It looks like the same behavior, but with a different implementation. Aug 4, 2021 at 20:52
  • 1
    Ok. FWIW, Perhaps remove/modify first sentence "All of the answers here work great if your divisor is positive, but it's not quite complete.", as it is not accurate. dCastro's answer existed at the time this was written. Perhaps it was buried fairly low at that time... Aug 4, 2021 at 21:06
1

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.

0

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

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;
1
  • 3
    I find this obscure; so much so that at first I thought it was wrong. I see no benefit to making this a single expression. It still contains a conditional so wouldn't be a significant performance benefit. IMHO better to do the easier-to-understand equivalent: { a %= n; if (a < 0) a += n; }. Or if using a conditional, stick with the earlier linked answer by Evgeni - which avoids the add on one of the two condition branches (and imho is easier to understand). Aug 3, 2021 at 14:24
0

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 
}