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

User · Answer

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

User · Answer

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 gt  0    mod   mod   arrayLength

User · Answer

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

User · Answer

A single line implementation of dcastro s answer  the most compliant with other languages    int Mod int a  int n        return    a    n   lt  0   amp  amp  n  gt  0      a  gt  0  amp  amp  n  lt  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   lt  0   amp  amp  n  gt  0      a  gt  0  amp  amp  n  lt  0    a   n   a             public static implicit operator int IntM i    gt  i  value      public static implicit operator IntM int i    gt  new IntM i       public static int operator   IntM a  int n    gt  Mod a  n       public static int operator   int a  IntM n    gt  Mod a  n       Use case  both works   int r    IntM a   n      Or int r   a   n IntM

User · Answer

ShreevatsaR s answer won t work for all cases  even if you add  if m lt 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  gt  0  amp  amp  remainder  lt  0                  n  lt  0  amp  amp  remainder  gt  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 lt ArgumentOutOfRangeException gt       gt  1 Mod 0               public static IEnumerable lt object   gt  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

User · Answer

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   lt  0    k n   k   As for performance cost of cast to uint have a look here

User · Answer

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    gt     a    n   lt  0    n   0    a

User · Answer

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

User · Answer

Just add your modulus  arrayLength  to the negative result of   and you ll be fine

User · Answer

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

User · Answer

Single-line implementation using   only once   int mod int k  int n     return   k    n   lt  0    k n   k

User · Answer

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           lt summary gt          Performs a canonical Modulus operation  where the output is on the range  0  b            lt  summary gt      public static real t PosMod real t a  real t b                real t c   a   b          if   c  lt  0  amp  amp  b  gt  0      c  gt  0  amp  amp  b  lt  0                          c    b                    return c           where real t can be any number type

User · Answer

Comparing two predominant answers   x m   m  m    and  int r   x m  return r lt 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

[c#] Mod of negative number is melting my brain

Examples related to c#

Examples related to math

Examples related to modulo