Python-style integer division & modulus in C

Question

In Python and Ruby, signed integer division truncates towards negative infinity, and signed integer modulus has the same sign the second operand:

>>> (-41) / 3
-14
>>> (-41) % 3
1

However, in C and Java, signed integer division truncates towards 0, and signed integer modulus has the same sign as the first operand:

printf("%d\n", (-41) / 3); /* prints "-13" */
printf("%d\n", (-41) % 3); /* prints "-2" */

What is the simplest and most efficient way in C to perform the same kind of division and modulus as in Python and Ruby?

Answer 1

It delves into the ugly world of floats, but these give correct answers in Java:

public static int pythonDiv(int a, int b) {
    if (!((a < 0) ^ (b < 0))) {
        return a / b;
    }
    return (int)(Math.floor((double)a/(double)b));
}

public static int pythonMod(int a, int b) {
    return a - b * pythonDiv(a,b);
}

I make no assertions about their efficiency.

Answer 2

The direction for rounding with signed integer division is not specified in older C standards. However, in C99 it is specified to round towards zero.

Here's portable code which works with all versions of the C standards and CPU architectures:

int py_div(int a, int b)
{
  if (a < 0)
    if (b < 0)
      return -a / -b;
    else
      return -(-a / b) - (-a % b != 0 ? 1 : 0);
  else if (b < 0)
      return -(a / -b) - (a % -b != 0 ? 1 : 0);
    else
      return a / b;
}

int py_mod(int a, int b)
{
  if (a < 0)
    if (b < 0)
      return -(-a % -b);
    else
      return -a % b - (-a % -b != 0 ? 1 : 0);
  else if (b < 0)
      return -(a % -b) + (-a % -b != 0 ? 1 : 0);
    else
      return a % b;
}

I did some superficial tests and it appears to give the same results as Python. This code may not be maximally efficient, but a good C compiler can probably optimize it adequately, especially if you put the code in a header as static functions.

You may also want to take a look at this closely related question: Integer division rounding with negatives in C++.

Answer 3

For modulo, I find the following simplest. It doesn't matter what the implementation's sign convention is, we just coerce the result to the sign we want:

r = n % a;
if (r < 0) r += a;

Obviously that's for positive a. For negative a you need:

r = n % a;
if (r > 0) r += a;

Which (perhaps a little confusingly) combines to give the following (in C++. In C do the same thing with int, and then tediously write a duplicate for long long):

template<typename T> T sign(T t) { return t > T(0) ? T(1) : T(-1); }

template<typename T> T py_mod(T n, T a) {
    T r = n % a;
    if (r * sign(a) < T(0)) r += a;
    return r;
}

We can use a cheapskate two-valued "sign" function because we already know a!=0, or the % would be undefined.

Applying the same principle to division (look at the output rather than the input):

q = n / a;
// assuming round-toward-zero
if ((q < 0) && (q * a != n)) --q;

The multiplications arguably could be more expensive than necessary, but can be micro-optimised later on a per-architecture basis if need be. For instance if you have a division op that gives you quotient and remainder, then you're sorted for division.

[Edit: there might be some edge cases where this goes wrong, for instance if the quotient or the remainder is INT_MAX or INT_MIN. But emulating python maths for large values is a whole other question anyway ;-)]

[Another edit: isn't the standard python implementation written in C? You could trawl the source for what they do]