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

Gerah

See the discussion about mathematical modulus on math.stackexchange.com/questions/519845/… – Eskil

blogs.msdn.microsoft.com/ericlippert/2011/12/05/… is a great article – Campanology

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.

Treiber

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. – Treiber

If you are going to check the value of m, you should also exclude zero. – Martyrize

@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 – Treiber

@ShreevatsaR: I edited it for readability. Since you insist, I'll leave your posts as-is. – Here

I believe you have missed something. What if x = -5 and m = 2? Since x is negative it will do r+m, but then the result will still be negative. You can easily fix it by adding while(x<0) r+m. – Ticklish

@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. – Treiber

@Treiber Actually, adding "if(m<0) m=-m;" isn't sufficient, the formula will return 8 for -12 mod -10, when it should return -2. See my answer below. – Chitwood

Just as a side note, there's basically no circumstances in the world where one call to mod and one branch is going to be faster than two calls to mod. – Recurved

@dcastro: I do want -12 mod -10 to be 8. This is the most common convention in mathematics, that if picking a representative r for a modulo b, then it is such that 0 ≤ r < |b|. – Treiber

Ive found plenty of other languages that return -2 for -12 mod -10, see below. – Chitwood

+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. – Hyssop

@BrettHale Agreed. It's also useful for doing circular buffers. I.e. index = index_of(value, values); value = values[(index - 1) % values.length]; Assuming you can't negatively index arrays, this crashes if the modulus operator can return negatives. – Washing

I also agree with BrettHale, however since the name "mod" is casually used to mean different things (and it's not generally clear what in a programming context) I would advocate that the method be named CommonResidue(int @base, int mod) for correctness and least ambiguity. (http://mathworld.wolfram.com/CommonResidue.html) – Iolenta

For what it's worth, did a quick mega-iteration, high resolution timer test of the two answers listed at the head of this answer, and return (x%m + m)%m; has a slight, consistent performance advantage between the two, on my system using C#, .NET CLR 4.0. – Fluoroscopy

@JoeBlow Please reread the last paragraph of the answer, which starts with "The reason it works is that "x%m" is always in the range [-m+1, m-1]." You can work it out yourself with a few examples if you're not convinced. (Edit: Also, see my comment to RuudLenders from Jan 2013 which addresses exactly the same misunderstanding as yours.) – Treiber

hi @Treiber I'm very sorry, it's my mistake - I didn't see the first "%m". Sorry again! Of course your answer is correct. – Maurita

This has a problem with overflow. If for example x = 1073741824 m = 1073741825 then this should give 1073741824 . However it actually gives you -1073741822. This also means that any improvements to the jitter can't improve this since it would change the semantics. So the if version is probably better to use. – Pileup

@KeithIrwin: Just tested on my i5, branch variant is nearly 2x faster than double % for me. – Krishnakrishnah

@Krishnakrishnah Are you testing that with situations where the argument may be either positive or negative so that the branch predictor doesn't simply train on one case? If so that's very interesting and I'd be curious to see what they did with the processor design to accomplish that because it seems inconceivable to me. – Recurved

@KeithIrwin: I re-tested on array of pregenerated random numbers, same results, only slightly lower difference. – Krishnakrishnah

your formula works only for whole numbers however in most languages. – Atrium

@Петър Петров - In what language does this not work for non-whole values? (Assuming positive m.) By mathematical definition, any language's mod operator must return some congruent value (that differs from x by a multiple of m). All languages that I know of return a value within range [-m, m). Adding m to that retains congruence, and ensures a non-negative value in [0, 2m). Taking modulus of that gives the desired congruent value in range [0, m). It would be a fundamental error in the language, if this formula did not work. – Bedbug

Why not just (x + m)%m ? Why have the 2nd % operator? – Sememe

@Sememe Your suggestion of (x + m)%m will work only when (x + m) is guaranteed to be nonnegative, i.e. when x >= -m. For the example in the question where x is -4 and m is 3, this does not hold. – Treiber

@Treiber - correct, I realized that after I posted my comment. Sorry. – Sememe

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.

Abernethy

"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. – Rightminded

"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). – Isidroisinglass

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 :) – Atrium

Why would anyone want to use the remainder function instead of a modulo? Why did they make % remainder? – Bork

@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. – Bedbug

Just for posterity: I struggled with the Math behind this until I realised that floor(-0.5) is -1 and not 0. – Kamerun

Alto this firmula supports non-integer divisor. e,g, it will snap to 0.5 if you pass b to be 0.5. – Atrium

after trying lots of things, I like this a lot. basically, find the "most recent" multiple of the divisor and subtract that multiple from the value. – Beghard

@ПетърПетров, by a definition of the modulus the -1 and 3 are the same number, just written differently. Also, it looks like you do not understand math very well, because a remainder can not be negative. While in your case you are claiming the -1 to be a remainder. – Bare

The great thing about this formula is that it works not only with integers, as most of the other answers do. – Tang

Answer 3

Single-line implementation using % only once:

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

Scrivens

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? – Depressomotor

@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 :) – Scrivens

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. – Scrivens

But is a single % more expensive than a test and jump, especially if it can't easily be predicted? – Anesthetist

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.

Sirree

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

Chitwood

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...) – Treiber

(...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. – Treiber

@Treiber 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. – Chitwood

Also, to add to the list: Scheme and Javascript – Chitwood

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". – Treiber

what about complex numbers too! – Eudocia

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. – Treiber

I like this answer. However, I disagree with the phrase 'ShreevatsaR's answer won't work for all cases". Technically, all computer language implementations are "correct", in that they return a value that is "congruent" with the inputs. As the Wikipedia article points out, there are TWO congruent values within the range [-m, m). BOTH of those are "correct" mathematically. Its simply a matter of convention, or of what your program expects, which of those two values is desired, for the rare case of m < 0. – Bedbug

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.

Reverberate

-1: not general enough, (and it is very easy to give a more general solution). – Scrivens

This is actually very helpful. when you have meaningful range, this can simplify computation. in my case math.stackexchange.com/questions/2279751/… – Jodiejodo

Exactly, just used this for dayOfWeek calculation (known range of -6 to +6) and it saved having two %. – Serration

@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) – Termor

Answer 7

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

Seawards

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

Holly

What does this add, that is not already covered by existing answers? – Bedbug

@Bedbug 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. – Holly

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

Nicks

I'm confused... you say that the result should always be positive, but then list the output as -1? – Miscellanea

@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.` – Nicks

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. – Bedbug

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

Gereron

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. – Inapt

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). – Rashid

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.) – Bedbug

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)

Bork

How is this different than dcastro's answer? – Bedbug

@Bedbug It looks like the same behavior, but with a different implementation. – Bork

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... – Bedbug

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.

Decasyllable

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

Termor

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;

Copolymer

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). – Bedbug

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 
}

Socalled