Time complexity of modulo operator in Python

Question

I am trying to determine the time complexity of an algorithm that I have, but I need first to know the time complexity of the % (modulo) operator in Python.

According to this post on http://math.stackexchange.com, its time complexity could be something similar to O(log m log n), and in some specific cases it could also be optimised to be constant, but I would like to know if someone really knows the time complexity of %, so that I can determine correctly the overall time complexity of my algorithm.

Of course I am aware that the complexity could change from implementation to implementation, but I am interested only in the standard implementation.

Answer 1

It's not that easy to determine, because if we speak about integer math, cpython uses different optimizations(for example for integers not exceeding the machine word it may be O(1) and for others it may be other). So there are two ways: first is looking into cpython sources and the second is measuring performance(for example with timeit) and then building extrapolation curve based on experimental points. The second method is better, because you would get an exact result, rather than a guess. For simple purposes, building a plot of experimental points should be enough, and if you want more, you may also use some regression analysis methods(like least-squares polynomial fitting).

Here's source of int implementation in cpython (look for long_divrem and x_divrem routines): https://hg.python.org/cpython/file/tip/Objects/longobject.c

Added: For unsigned int modulo its used algorithm from Knuth's book, which is O(MN) where M+1 is number of machine words in the quotient and N is number of machine words in remainder. For signed it's used own implementation

Answer 2

For large integers, Python division (and modulo) use an O(n^2) algorithm. Multiplication uses the Karatsuba multiplication which is O(n^1.585) but division uses basic "grade-school" division.