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

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 2

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]

Answer 3

There is a solution to this question that is much shorter (in code) than the already presented ones. I will use the format of Ville Laurikari's answer for mine:

int py_div(int a, int b)
{
    return (a - (((a % b) + b) % b)) / b);
}

int py_mod(int a, int b)
{
    return ((a % b) + b) % b;
}

Unfortunately, it seems that the above solutions are not performing well. When benchmarking this solution against the one of Ville Laurikari, it becomes apparent that this solution performs only half as fast.

The lesson is: While branching instructions make code slow, division instructions are much worse!

I thought I nevertheless post this solution if only for its elegance.

Answer 4

Here is a simple implementation of floored division and modulus in C89:

#include <stdlib.h>

div_t div_floor(int x, int y)
{
    div_t r = div(x, y);
    if (r.rem && (x < 0) != (y < 0)) {
        r.quot -= 1;
        r.rem  += y;
    }
    return r;
}

Here, div is used because it has well-defined behavior.

If you're using C++11, here is a templated implementation of floored division and modulus:

#include <tuple>

template<class Integral>
std::tuple<Integral, Integral> div_floor(Integral x, Integral y)
{
    typedef std::tuple<Integral, Integral> result_type;
    const Integral quot = x / y;
    const Integral rem  = x % y;
    if (rem && (x < 0) != (y < 0))
        return result_type(quot - 1, rem + y);
    return result_type(quot, rem);
}

In C99 and C++11, you can avoid using div since the behavior of division and modulus in C are no longer depend on the implementation.