python - Python是如何实现取模运算的？

Question

我对%Python 中运算符的时间和空间复杂性很好奇。另外，Python 是否对 ? 使用按位运算% 2？

编辑： 我问的是 Python 2.7 的实现，以防它与 Python 3 略有不同

Answer 1

Python 使用 Knuth 的“计算机编程艺术”中的经典算法 D。运行时间（通常）与两个数字的长度的乘积成正比。空间与两个数字的长度之和成正比。

实际除法发生在 中Objects/longobject.c，请参见x_divrem()。有关 Python long 的内部表示的背景信息，请参阅Include/longintrepr.h.

% 2不使用按位运算。检查数字是否为偶数/奇数的标准习语是& 1.

Python 2 和 3 使用相同的算法。

Answer 2

2.7 版的 python 文档 ( http://docs.python.org/2.7/library/functions.html?highlight=divmod#divmod ) 有一些关于此的基本信息。

我还看了一下源代码；我还不足以真正解释发生了什么，但 Objects\abstract.c 将“divmod()”定义为二进制函数。

在第 1246 行，为余数定义了一个函数：

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

binary_op 函数在第 994 行定义，主要包装在第 922 行定义的函数“binary_op1”。从那里，大部分代码运行到第 895 行定义的名为“NB_BINOP”的函数，如下面的代码所示：

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

我的知识从那里用完了，但希望能提供一些见解。