python整数运算_深入 Python (6) 整数对象的数学运算

整数的基本运算

上一节讲到，在 PyLong_Type 中定义了整数类型的各种属性，比如整数类型的名称 “int”。整数对象最常用的是一些数学运算，整数对象当然也是支持这些方法的，它们定义在：

// Object/longobject.c:5632

PyTypeObject PyLong_Type = {

PyVarObject_HEAD_INIT(&PyType_Type, 0)

"int", /* tp_name */

offsetof(PyLongObject, ob_digit), /* tp_basicsize */

sizeof(digit), /* tp_itemsize */

0, /* tp_dealloc */

0, /* tp_vectorcall_offset */

0, /* tp_getattr */

0, /* tp_setattr */

0, /* tp_as_async */

long_to_decimal_string, /* tp_repr */

&long_as_number, /* tp_as_number */

/*

************忽略了一些代码************

*/

PyObject_Del, /* tp_free */

};

注意其中 &long_as_number 一行，它是一个函数指针数组，其中定义了整数的一系列数学方法，我们在用整数对象进行数学计算的时候，实质上调用的是这个数组里的指针。

// Object/longobject.c:5595，就在 PyLong_Type 定义上方

static PyNumberMethods long_as_number = {

(binaryfunc)long_add, /*nb_add*/

(binaryfunc)long_sub, /*nb_subtract*/

(binaryfunc)long_mul, /*nb_multiply*/

long_mod, /*nb_remainder*/

long_divmod, /*nb_divmod*/

long_pow, /*nb_power*/

(unaryfunc)long_neg, /*nb_negative*/

long_long, /*tp_positive*/

(unaryfunc)long_abs, /*tp_absolute*/

(inquiry)long_bool, /*tp_bool*/

(unaryfunc)long_invert, /*nb_invert*/

long_lshift, /*nb_lshift*/

long_rshift, /*nb_rshift*/

long_and, /*nb_and*/

long_xor, /*nb_xor*/

long_or, /*nb_or*/

long_long, /*nb_int*/

0, /*nb_reserved*/

long_float, /*nb_float*/

0, /* nb_inplace_add */

0, /* nb_inplace_subtract */

0, /* nb_inplace_multiply */

0, /* nb_inplace_remainder */

0, /* nb_inplace_power */

0, /* nb_inplace_lshift */

0, /* nb_inplace_rshift */

0, /* nb_inplace_and */

0, /* nb_inplace_xor */

0, /* nb_inplace_or */

long_div, /* nb_floor_divide */

long_true_divide, /* nb_true_divide */

0, /* nb_inplace_floor_divide */

0, /* nb_inplace_true_divide */

long_long, /* nb_index */

};

通过结构体成员的命名就可以大致看出这些函数的作用，注意到其中一些方法没有实现，被设置为 0，这些是目前整数对象不支持的方法。绝大多数函数功能都不是很复杂，这里以比较复杂的乘法稍作解释。

乘法的实现

第一种，也是最简单的，对于那些大小在 1 digit 的整数，直接通过 a * b 计算，一条 CPU 指令就可以得到结果。

第二种稍微复杂一点，对于那些不能在一个寄存器宽度内计算的长整数，可以采用算式模拟（gradeschool math）。其原理非常简单，需要回顾小学的乘法竖式。假如 a = 123, b = 45, 计算 a * b.

将两个长整数乘法转换为一个长整数与 1 位整数按位相乘，结果求和的过程。这个方法不仅在 10 进制下，其他进制下也是成立的。

第三种是 Python 实现用用到的 Karatsuba 算法，这是一种快速实现长整数乘法的算法。其基本原理是将长整数按照一个基数 X 分解为 high、low 两部分，对于两个长整数 a，b 有：

其中

，这样就把一个长整数乘法转换为：

三个长度更短的整数运算，利用递归思想，长整数的运算很快被转换为一系列短整数乘法。

整数乘法的优化

Python 在实现整数乘法时做了三个优化，

第一个：

// Object/longobject.c:3551

static PyObject *

long_mul(PyLongObject *a, PyLongObject *b)

{

PyLongObject *z;

CHECK_BINOP(a, b);

/* fast path for single-digit multiplication */

if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {

stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);

return PyLong_FromLongLong((long long)v);

}

z = k_mul(a, b);

/* Negate if exactly one of the inputs is negative. */

if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z) {

_PyLong_Negate(&z);

if (z == NULL)

return NULL;

}

return (PyObject *)z;

}

如果整数的长度只有一个 digit，也就是 30 bits，那么就可以走捷径，直接用 C 语言内置乘法计算结果，仅从计算效率上来说，与 C 语言一样。

第二，如果整数长度大于 1 个 digit，那么就去 k_mul 函数：

/* Karatsuba multiplication. Ignores the input signs, and returns the

* absolute value of the product (or NULL if error).

* See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).

*/

static PyLongObject *

k_mul(PyLongObject *a, PyLongObject *b)

{

Py_ssize_t asize = Py_ABS(Py_SIZE(a));

Py_ssize_t bsize = Py_ABS(Py_SIZE(b));

PyLongObject *ah = NULL;

PyLongObject *al = NULL;

PyLongObject *bh = NULL;

PyLongObject *bl = NULL;

PyLongObject *ret = NULL;

PyLongObject *t1, *t2, *t3;

Py_ssize_t shift; /* the number of digits we split off */

Py_ssize_t i;

/* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl

* Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl

* Then the original product is

* ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl

* By picking X to be a power of 2, "*X" is just shifting, and it's

* been reduced to 3 multiplies on numbers half the size.

*/

/* We want to split based on the larger number; fiddle so that b

* is largest.

*/

if (asize > bsize) {

t1 = a;

a = b;

b = t1;

i = asize;

asize = bsize;

bsize = i;

}

/* Use gradeschool math when either number is too small. */

i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;

if (asize <= i) {

if (asize == 0)

return (PyLongObject *)PyLong_FromLong(0);

else

return x_mul(a, b);

}

// 下面是 Karatsuba 算法，代码较多不再贴出来

注释中简要描述了 Karatsuba 算法的步骤，如果 a、b 的长度小于一个阈值，那么就使用 gradeschool math 算法计算长整数乘法，这么做的主要原因是低于这个阈值 Karatsuba 算法不再有优势，另外，这个条件也是 k_mul 函数递归调用的退出条件，否则递归永远不会结束。

第三，对于更长的整数乘法会使用 Karatsuba 算法计算，前一部分介绍 Karatsuba 算法已经看到，Karatsuba 算法是将长整数拆分为若干个短整数的乘法和加法，其中乘法会尝试递归使用 Karatsuba 算法，直到拆分到足够短的整数，满足条件结束递归。

关注我，了解程序员的烧脑日常，还有开源 Python 教程。

最后

以上就是从容月饼为你收集整理的python整数运算_深入 Python (6) 整数对象的数学运算的全部内容，希望文章能够帮你解决python整数运算_深入 Python (6) 整数对象的数学运算所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。