Python如何实现取模运算？

Question

我对Python中%运算符的时间和空间复杂度很感兴趣。此外，Python是否对% 2使用位运算？

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

- sgarza62

Answer 1

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

实际的除法在Objects/longobject.c中进行，参见x_divrem()。关于Python长整数的内部表示的背景信息，请参见Include/longintrepr.h。

% 2不使用位运算。检查一个数字是否为偶数/奇数的标准惯用法是& 1。

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

- casevh

---

请问您能否提供找到这个信息的文档或源代码的链接？我很想看一下。 - sgarza62

这句话的意思是它的时间复杂度为O(n*x)，其中n是被除数，x是除数？ - Draconar

@Draconar 运行时间为O(n*x)，其中n是被除数的长度，x是除数的长度。除非另有说明，大多数关于除法算法运行时间的讨论都假定被除数是除数的两倍长。Python的除法算法被认为是O(n^2)。 - casevh

@casevh 对不起，我很无知，请问您所说的长度是指涉及到的数字有多少位？ - Draconar

@Draconar，所谓长度，是指数字中的位数（或十进制位数）。在Python中，除法和取模都是O(n^2)算法。将一个2000位数除以一个1000位数大约需要比将一个1000位数除以一个500位数多4倍的时间。如果您继续将数字的位数加倍，这个比率将变得更接近于4。 - casevh

Answer 2

Python 2.7的文档(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”。从那里开始，大部分代码运行到一个名为“NB_BINOP”的函数，该函数在下面的代码中定义在第895行：

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

我的知识就到这里了，但希望这能提供一些想法。

- Dragonsdoom