Python-style integer division & modulus in C

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]

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.

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.

The question asked about how to emulate Python-style integer division and modulo. All of the answers given here assume the operands of this operation to be integers themselves but Python can also use floats for its modulo operation. Thus, I think the following answer solves the problem even better:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int pydiv(double a, double b) {
    int q = a/b;
    double r = fmod(a,b);
    if ((r != 0) && ((r < 0) != (b < 0))) {
        q -= 1;
    }
    return q;
}

int main(int argc, char* argv[])
{
    double a = atof(argv[1]);
    double b = atof(argv[2]);
    printf("%d\n", pydiv(a, b));
}

And for the modulo:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

double pymod(double a, double b) {
    double r = fmod(a, b);
    if (r!=0 && ((r<0) != (b<0))) {
        r += b;
    }
    return r;
}

int main(int argc, char* argv[])
{
    double a = atof(argv[1]);
    double b = atof(argv[2]);
    printf("%f\n", pymod(a, b));
}

I tested the above two programs against how Python behaves using the following test code:

#!/usr/bin/python3
import subprocess
subprocess.call(["cc", "pydiv.c", "-lm", "-o", "cdiv"])
subprocess.call(["cc", "pymod.c", "-lm", "-o", "cmod"])
def frange(start, stop, step=1):
    for i in range(0, int((stop-start)/step)):
        yield start + step*i
for a in frange(-10.0, 10.0, 0.25):
    for b in frange(-10.0, 10.0, 0.25):
        if (b == 0.0):
            continue
        pydiv = a//b
        pymod = a%b
        cdiv = int(subprocess.check_output(["./cdiv", str(a), str(b)]))
        cmod = float(subprocess.check_output(["./cmod", str(a), str(b)]))
        if pydiv != cdiv:
            exit(1)
        if pymod != cmod:
            exit(1)

The above will compare the behaviour of Python division and modulo with the C implementations I presented on 6320 testcases. Since the comparison succeeded, I believe that my solution correctly implements Python's behaviour of the respective operations.

Since nobody has posted it yet, here is the actual code from Python (Python-3.12.1/Objects/longobject.c:3982). Note that Python "digits" are always positive, with the sign stored separately, so left and right are the absolute values of the two arguments.

/* Fast floor division for single-digit longs. */
static PyObject *
fast_floor_div(PyLongObject *a, PyLongObject *b)
{
    sdigit left = a->long_value.ob_digit[0];
    sdigit right = b->long_value.ob_digit[0];
    sdigit div;

    assert(_PyLong_DigitCount(a) == 1);
    assert(_PyLong_DigitCount(b) == 1);

    if (_PyLong_SameSign(a, b)) {
        div = left / right;
    }
    else {
        /* Either 'a' or 'b' is negative. */
        div = -1 - (left - 1) / right;
    }

    return PyLong_FromLong(div);
}

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.