Временная сложность оператора modulo в Python

Question

Я пытаюсь определить временную сложность алгоритма, который у меня есть, но мне нужно сначала узнать временную сложность оператора% (modulo) в Python.

Согласно this post на http://math.stackexchange.com, его временная сложность может быть что-то похожее на O(log m log n), а в некоторых конкретных случаях это может также быть оптимизированы, чтобы быть постоянным, но я хотел бы знать, если кто-то действительно знает временную сложность %, так что я могу правильно определить общую временную сложность моего алгоритма.

Конечно, я знаю, что сложность может измениться с реализации на реализацию, но меня интересует только стандартная реализация.

Answer 1

Это не так просто определить, потому что если мы говорим о целочисленной математике, cpython использует различные оптимизации (например, для целых чисел, не превышающих машинное слово, это может быть O (1), а для других это может быть другое). Таким образом, существует два способа: сначала изучать источники cpython, а второй - измерять производительность (например, с помощью timeit), а затем строить кривую экстраполяции на основе экспериментальных точек. Второй метод лучше, потому что вы получите точный результат, а не предположение. Для простых целей достаточно построить график экспериментальных точек, и если вы хотите больше, вы можете также использовать некоторые методы регрессионного анализа (например, полиномиальное подмножество наименьших квадратов).

Вот источник реализации ИНТ в CPython (ищите long_divrem и x_divrem рутин): https://hg.python.org/cpython/file/tip/Objects/longobject.c

Добавлено: Для неподписанных Int по модулю используется алгоритм из книги Кнута, который является O (MN), где M + 1 является количество машинных слов в частном, а N - количество машинных слов в остатке. Для подписанной используется собственная реализация

Answer 2

Для больших целых чисел деление Python (и по модулю) использует алгоритм O (n^2). Умножение использует умножение Карацубы, которое равно O (n^1.585), но деление использует основное разделение «классной школы».