How does Python implement the modulo operation?

Question

I'm curious in regards to the time and space complexities of the % operator in Python. Also, does Python use a bitwise operation for % 2?

Edit: I'm asking about Python 2.7's implementation, just in case it differs slightly from that of Python 3

Answer 1

Python uses the classic Algorithm D from Knuth's 'The Art of Computer Programming'. The running time is (generally) proportional to the product of lengths of the two numbers. Space is proportional to the sum of the lengths of the two numbers.

The actual division occurs in Objects/longobject.c, see x_divrem(). For background on the internal representation of a Python long, see Include/longintrepr.h.

% 2 does not use bitwise operations. The standard idiom for checking if a number is even/odd is & 1.

Python 2 and 3 use the same algorithm.

Answer 2

The python documentation (http://docs.python.org/2.7/library/functions.html?highlight=divmod#divmod) for version 2.7 has some basic information about this.

I also took a look at the source code; I'm not enough of an expert to really explain what's going on, but Objects\abstract.c defines "divmod()" as a binary function.

On line 1246, a function is defined for remainder:

PyObject *
PyNumber_Remainder(PyObject *v, PyObject *w)
{
    return binary_op(v, w, NB_SLOT(nb_remainder), "%");
}

The binary_op function is defined on line 994, and primarily wraps the function "binary_op1" defined on line 922. From there, most of the code runs to a function called "NB_BINOP" defined on line 895 as shown in the below code:

#define NB_BINOP(nb_methods, slot) \
(*(binaryfunc*)(& ((char*)nb_methods)[slot]))

My knowledge runs out from there, but hopefully that provides some insight.