Python-style integer division and module in C

Question

In Python and Ruby, signed integer division is rounded to negative infinity, and a signed integer module has the same sign as the second operand:

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

However, in C and Java, signed integer division is divided by 0, and signed integer module 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 easiest and most efficient way in C to do the same type of division and module as in Python and Ruby?

Answer 1

The rounding direction with an integer sign is not specified in the old C standards. However, C99 indicates rounding to zero.

Here's portable code that works with all versions of C standards and processor architecture:

 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 surface tests and seemed to give the same results as Python. This code may not be as efficient as possible, but a good C compiler can probably optimize it, especially if you enter the code in the header as static functions.

You can also take a look at this close question: Integer division of rounding with negatives in C ++ .

Answer 2

For modulo, I find the following simplest. No matter what the implementation declaration agreement means, we simply force the result to the sign we need:

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

Obviously, for positive a. For negative, you need:

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

Which (perhaps a little vaguely) combines to give the following (in C ++. In C, doing the same with int and then tiring to write a duplicate for a long time):

 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 the two-digit sign function cheapskate because we already know a! = 0, or% will be undefined.

Applying the same principle to division (look at the output, not the input):

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

Multiplications may possibly be more expensive than necessary, but if necessary they can be optimized with a micro-level structure based on each architecture. For example, if you have a division operation that gives you a ratio and a remainder, then you are sorted for division.

[Edit: there may be some cross cases where this does not happen, for example, if the quotient or the rest is INT_MAX or INT_MIN. But emulating python math for large values ​​is another question :-)]

[Other editing: not a standard python implementation written in C? You can trawl the source for what they do]

Answer 3

Here is a simple implementation of the floor-split and module 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; } 

A div used here because it has the correct behavior .

If you are using C ++ 11, this is a template implementation of a floor-split and module:

 #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 a div , since the division and module behavior in C is no longer implementation dependent.

Answer 4

There is a solution to this issue, which is much shorter (in code) than those already presented. I will use the Ville Laurikari response format 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, the above solutions do not seem to work well. When comparing this solution with Ville Laurikari, it becomes obvious that this solution only works half as fast.

Lesson: While branching instructions make code slow, separation instructions are much worse!

I thought I was still posting this solution, if only for its elegance.

Answer 5

The question is how to emulate integer division and modulo in Python style. All of the answers given here assume that the operands of this operation are integers, but Python can also use float for its modular operation. So, 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 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 two programs above against how Python behaves with 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 behavior of Python division and modulo with C implementations that I presented on 6320 test sites. Since the comparison was successful, I believe that my solution correctly implements the behavior of Python related operations.

Answer 6

It penetrates the ugly world of floaters, but they give the 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 do not claim their effectiveness.