operators - 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.