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

Solution 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.

Solution 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.

Solution 3

Single-line implementation using % only once:

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

Solution 4

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.

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

View more solutions

Comments

[PPC]

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

[Samra]

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

[Renzo]

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

[leetNightshade]

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

[sidgeon smythe]

@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

[Daniel A.A. Pelsmaeker]

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

[Rudey]

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.

[sidgeon smythe]

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

[dcastro]

@ShreevatsaR 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.

[Keith Irwin]

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.

[sidgeon smythe]

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

[sidgeon smythe]

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

[sidgeon smythe]

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

[dcastro]

@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]

Also, to add to the list: Scheme and Javascript

[dcastro]

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

[Brett Hale]

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

[Evgeni Sergeev]

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

[Tyress]

"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, 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 :)

[Sandy Chapman]

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

[AnorZaken]

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)

[dapi]

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.

[Jeff B]

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

[I liked the old Stack Overflow]

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.

[Abin]

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

[sidgeon smythe]

@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.)

[Fattie]

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

[poizan42]

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.

[John Demetriou]

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?

[Evgeni Sergeev]

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

[Evgeni Sergeev]

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.

[sidgeon smythe]

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

[j_schultz]

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

[M.kazem Akhgary]

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

[Medinoc]

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

[Aaron Franke]

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

[Youda008]

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

[Keith Irwin]

@Youda008 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.

[Youda008]

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

[Martin Capodici]

what about complex numbers too!

[ToolmakerSteve]

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

[NetMage]

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

[sidgeon smythe]

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.

[nobody]

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

[Петър Петров]

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

[Петър Петров]

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

[Erdal G.]

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

[Dave Cousineau]

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.

[ToolmakerSteve]

@Петър Петров - 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.

[ToolmakerSteve]

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.

[ToolmakerSteve]

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.

[ToolmakerSteve]

How is this different than dcastro's answer?

[ToolmakerSteve]

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

[ToolmakerSteve]

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

[Aaron Franke]

@ToolmakerSteve It looks like the same behavior, but with a different implementation.

[ToolmakerSteve]

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

[ToolmakerSteve]

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

[Andrew]

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

[qqqqqqq]

@ПетърПетров, 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.

[JAlex]

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

[sidgeon smythe]

@JAlex 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.

[JAlex]

@ShreevatsaR - correct, I realized that after I posted my comment. Sorry.