How to code a modulo operator in C C Obj-C that handles negative numbers

Question

One of my pet hates of C-derived languages  as a mathematician   is that   -1    8    comes out as -1  and not 7  fmodf -1 8     fails similarly   What s the best solution     C   allows the possibility of templates and operator overloading  but both of these are murky waters for me  examples gratefully received

User · Answer

This solution  for use when mod is positive  avoids taking negative divide or remainder operations all together   int core modulus int val  int mod        if val gt  0          return val   mod      else         return val   mod     mod - val - 1  mod

User · Answer

Here s a new answer to an old question  based on this Microsoft Research paper and references therein  Note that from C11 and C  11 onwards  the semantics of div has become truncation towards zero  see  expr mul  4   Furthermore  for D divided by d  C  11 guarantees the following about the quotient qT and remainder rT auto const qT   D   d  auto const rT   D   d  assert D    d   qT   rT   assert abs rT   lt  abs d    assert signum rT     signum D     rT    0    where signum maps to -1  0   1  depending on whether its argument is  lt        gt  than 0  see this Q amp A for source code   With truncated division  the sign of the remainder is equal to the sign of the dividend D  i e  -1   8    -1  C  11 also provides a std  div function that returns a struct with members quot and rem according to truncated division  There are other definitions possible  e g  so-called floored division can be defined in terms of the builtin truncated division auto const I   signum rT     -signum d    1   0  auto const qF   qT - I  auto const rF   rT   I   d  assert D    d   qF   rF   assert abs rF   lt  abs d    assert signum rF     signum d     With floored division  the sign of the remainder is equal to the sign of the divisor d  In languages such as Haskell and Oberon  there are builtin operators for floored division  In C    you d need to write a function using the above definitions  Yet another way is Euclidean division  which can also be defined in terms of the builtin truncated division auto const I   rT  gt   0   0    d  gt  0   1   -1   auto const qE   qT - I  auto const rE   rT   I   d  assert D    d   qE   rE   assert abs rE   lt  abs d    assert signum rE   gt   0    With Euclidean division  the sign of the remainder is always non-negative

User · Answer

Here is a C function that handles positive OR negative integer OR fractional values for BOTH OPERANDS   include  lt math h gt  float mod float a  float N   return a - N floor a N      return in range  0  N    This is surely the most elegant solution from a mathematical standpoint   However  I m not sure if it is robust in handling integers   Sometimes floating point errors creep in when converting int -  fp -  int   I am using this code for non-int s  and a separate function for int   NOTE  need to trap N   0    Tester code      include  lt math h gt   include  lt stdio h gt   float mod float a  float N        float ret   a - N   floor  a   N        printf   f 1 mod  f 1    f 1  n   a  N  ret        return ret     int main  char  argc  char   argv        printf   fmodf -10 2  2 0     f 1     FAIL   n n   fmodf -10 2  2 0         float x      x   mod 10 2f  2 0f       x   mod 10 2f  -2 0f       x   mod -10 2f  2 0f       x   mod -10 2f  -2 0f        return 0       Note  You can compile and run it straight out of CodePad  http   codepad org UOgEqAMA   Output        fmodf -10 2  2 0    -0 20     FAIL          10 2 mod 2 0   0 2   10 2 mod -2 0   -1 8   -10 2 mod 2 0   1 8   -10 2 mod -2 0   -0 2

User · Answer

Oh  I hate   design for this too      You may convert dividend to unsigned in a way like   unsigned int offset    -INT MIN  -  -INT MIN  divider  result    offset   dividend    divider   where offset is closest to  -INT MIN  multiple of module  so adding and subtracting it will not change modulo  Note that it have unsigned type and result will be integer  Unfortunately it cannot correctly convert values INT MIN    -offset-1  as they cause arifmetic overflow  But this method have advandage of only single additional arithmetic per operation  and no conditionals  when working with constant divider  so it is usable in DSP-like applications   There s special case  where divider is 2N  integer power of two   for which modulo can be calculated using simple arithmetic and bitwise logic as   dividend amp  divider-1    for example  x mod 2   x  amp  1 x mod 4   x  amp  3 x mod 8   x  amp  7 x mod 16   x  amp  15   More common and less tricky way is to get modulo using this function  works only with positive divider    int mod int x  int y        int r   x y      return r lt 0 r y r      This just correct result if it is negative   Also you may trick    p q   q  q  It is very short but use two  -s which are commonly slow

User · Answer

The simplest general function to find the positive modulo would be this- It would work on both positive and negative values of x   int modulo int x int N       return  x   N   N   N

User · Answer

First of all I d like to note that you cannot even rely on the fact that  -1    8    -1  the only thing you can rely on is that  x   y    y     x   y     x  However whether or not the remainder is negative is implementation-defined    Now why use templates here  An overload for ints and longs would do   int mod  int a  int b       int ret   a   b     if ret  lt  0       ret  b     return ret      and now you can call it like mod -1 8  and it will appear to be 7    Edit  I found a bug in my code  It won t work if b is negative  So I think this is better   int mod  int a  int b       if b  lt  0    you can check for b    0 separately and do what you want      return -mod -a  -b         int ret   a   b     if ret  lt  0       ret  b     return ret      Reference  C  03 paragraph 5 6 clause 4      The binary   operator yields the quotient  and the binary   operator yields the remainder from the division of the first expression by the second  If the second operand of   or   is zero the behavior is undefined  otherwise  a b  b   a b is equal to a  If both operands are nonnegative then the remainder is nonnegative  if not  the sign of the remainder is implementation-defined

User · Answer

Warning  macro mod evaluates its arguments  side effects multiple times      define mod r m     r     m       r  lt 0   m  0        or just get used to getting any representative for the equivalence class

User · Answer

unsigned mod int a  unsigned b        return  a  gt   0   a   b   b -  -a    b

User · Answer

For integers this is simple  Just do      x  lt  0      x   N    N    x    N    where I am supposing that N is positive and representable in the type of x  Your favorite compiler should be able to optimize this out  such that it ends up in just one mod operation in assembler

User · Answer

Example template for C    template lt  class T  gt  T mod  T a  T b         T const r   a b      return   r  0  amp  amp   r b  lt 0    r   b   r       With this template  the returned remainder will be zero or have the same sign as the divisor  denominator   the equivalent of rounding towards negative infinity   instead of the C   behavior of the remainder being zero or having the same sign as the dividend  numerator   the equivalent of rounding towards zero

User · Answer

The best solution   for a mathematician is to use Python    C   operator overloading has little to do with it  You can t overload operators for built-in types  What you want is simply a function  Of course you can use C   templating to implement that function for all relevant types with just 1 piece of code   The standard C library provides fmod  if I recall the name correctly  for floating point types   For integers you can define a C   function template that always returns non-negative remainder  corresponding to Euclidian division  as        include  lt stdlib h gt      abs  template lt  class Integer  gt  auto mod  Integer a  Integer b       - gt  Integer       Integer const r   a b      return  r  lt  0  r   abs  b     r           and just write mod a  b  instead of a b   Here the type Integer needs to be a signed integer type   If you want the common math behavior where the sign of the remainder is the same as the sign of the divisor  then you can do e g   template lt  class Integer  gt  auto floor div  Integer const a  Integer const b       - gt  Integer       bool const a is negative    a  lt  0       bool const b is negative    b  lt  0       bool const change sign     a is negative    b is negative        Integer const abs b           abs  b        Integer const abs a plus      abs  a      change sign  abs b - 1   0        Integer const quot   abs a plus   abs b      return  change sign  -quot   quot      template lt  class Integer  gt  auto floor mod  Integer const a  Integer const b       - gt  Integer   return a - b floor div  a  b         hellip  with the same constraint on Integer  that it s a signed type         Because Python s integer division rounds towards negative infinity

User · Answer

I believe another solution to this problem would be use to variables of type long instead of int    I was just working on some code where the   operator was returning a negative value which caused some issues  for generating uniform random variables on  0 1  you don t really want negative numbers       but after switching the variables to type long  everything was running smoothly and the results matched the ones I was getting when running the same code in python  important for me as I wanted to be able to generate the same  random  numbers across several platforms

User · Answer

I would do     -1  8    8    This adds the latter number to the first before doing the modulo giving 7 as desired  This should work for any number down to -8  For -9 add 2 8

User · Answer

I have just noticed that Bjarne Stroustrup labels   as the remainder operator  not the modulo operator   I would bet that this is its formal name in the ANSI C  amp  C   specifications  and that abuse of terminology has crept in   Does anyone know this for a fact   But if this is the case then C s fmodf   function  and probably others  are very misleading    they should be labelled fremf    etc

User · Answer

For a solution that uses no branches and only 1 mod  you can do the following     Works for other sizes too     assuming you change 63 to the appropriate value int64 t mod int64 t x  int64 t div      return  x   div       x  gt  gt  63     div  gt  gt  63    amp  div

User · Answer

define  MOD a  b            a   b    b    b

[c++] How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers

Examples related to c++

Examples related to c

Examples related to c++11

Examples related to operator-overloading

Examples related to modulo