ESON

Daily Notes

0%

Python 整数对象

发表于 分类于 ， ， ， ， ， ，
本文字数： 5.3k 阅读时长 ≈ 5 分钟

Python2 的整数对象 有 PyIntObject 和 PyLongObject 这两种类型，Python3 只保留了 PyLongObject。
这里我们介绍一下python3的PyLongObject。

1
2
3
4
5
6
7
8
9
10
Python 3.7.3 (default, Mar 27 2019, 22:11:17

# 类型
>>> a = 45
>>> type(a)
<class 'int'>

# 小整数


PyLongObject

1
2
3
4
5
6
7
8
9
10
11
PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name , 在python2中是long */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    long_dealloc,                               /* tp_dealloc */
    ...
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

我们可以看到，PyLong_Type类型对象的tp_name就是int，也就是说，在Python内部，它就是int类型。

源文件：Include/longobject.h

1
2
3
// longobject.h


源文件：Include/longintrepr.h

1
2
3
4
5
6
7
8
/* longobject.h  */
typedef struct _longobject PyLongObject;

/* longintrepr.h */
struct _longobject {
    PyVarObject ob_base;   // 即 PyObject_VAR_HEAD
    digit ob_digit[1];     // 
};

从源码可以看出 PyLongObject 是变长对象

类型对象 PyLong_Type

源文件：Objects/longobject.c

创建整数对象

从 PyLong_Type 可以看出，创建一个整数对象的入口函数为 long_new

源文件：Objects/clinic/longobject.c.h

从 long_new_impl 函数可以看出有如下几种情况

  • x == NULL 且 obase != NULL 调用 PyLong_FromLong
  • obase 为 NULL 调用 PyNumber_Long
  • x 和 obase 都不为 NULL
    • PyUnicode 调用 PyLong_FromUnicodeObject，最终调用 PyLong_FromString
    • PyByteArray/PyBytes 调用_PyLong_FromBytes，最终调用 PyLong_FromString

小整数对象

一些整数在一开始就会被初始化一直留存，当再次使用直接从小整数对象池中获取，不用频繁的申请内存。

默认的小整数范围是 [-5, 257) 源文件：Objects/longobject.c

get_small_int

宏 CHECK_SMALL_INT 会检查传入的数是否在小整数范围内，如果是直接返回。
可以在创建或复制整数对象等函数中找到 CHECK_SMALL_INT 的身影，以下只列出了
PyLong_FromLong，就不一一列举了

小整数初始化

源文件：Objects/longobject.c

_PyLong_Init

整数的存储结构

源文件：Objects/longobject.c

在 long_to_decimal_string_internal中添加如下代码并重新编译安装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Objects/longobject.c
static int
long_to_decimal_string_internal(PyObject *aa,
                                PyObject **p_output,
                                _PyUnicodeWriter *writer,
                                _PyBytesWriter *bytes_writer,
                                char **bytes_str)
{
    PyLongObject *scratch, *a;
    PyObject *str = NULL;
    Py_ssize_t size, strlen, size_a, i, j;
    digit *pout, *pin, rem, tenpow;
    int negative;
    int d;
    enum PyUnicode_Kind kind;

    a = (PyLongObject *)aa;

    // 添加打印代码
    printf("ob_size     = %d\n", Py_SIZE(a));
    for (int index = 0; index < Py_SIZE(a); ++index) {
        printf("ob_digit[%d] = %d\n", index, a->ob_digit[index]);
    }

    ...
}

编译安装后进入 python 解释器输入如下代码

1
2
3
4
5
6
7
8
9
num = 9223372043297226753
print(num)

# output
>>> ob_size     = 3
>>> ob_digit[0] = 1
>>> ob_digit[1] = 6
>>> ob_digit[2] = 8
>>> 9223372043297226753

如下图所示

longobject storage

注：这里的 30 是由 PyLong_SHIFT 决定的，64 位系统中，PyLong_SHIFT 为 30，否则 PyLong_SHIFT 为 15

整数对象的数值操作

整数相加

源文件：Objects/longobject.c

long_add

可以看到整数的加法运算函数 long_add 根据 a、b 的 ob_size 又细分为两个函数 (x_add 和 x_sub) 做处理

源文件：Objects/longobject.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Objects/longobject.c

/* Add the absolute values of two integers. */
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    digit carry = 0;

    /* Ensure a is the larger of the two: */
    // 确保 a 大于 b
    if (size_a < size_b) {
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    z = _PyLong_New(size_a+1);
    if (z == NULL)
        return NULL;
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
    return long_normalize(z);
}

加法运算函数 x_add 从 ob_digit 数组的低位开始依次按位相加，carry 做进位处理，然后处理 a 对象的高位数字，最后使用 long_normalize 函数调整 ob_size，确保 ob_digit[abs(ob_size)-1]不为零，这与普通四则运算的加法运算相同，只不过进位单元不同而已

longobject x_add

源文件：Objects/longobject.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// Objects/longobject.c

/* Subtract the absolute values of two integers. */

static PyLongObject *
x_sub(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    int sign = 1;
    digit borrow = 0;

    /* Ensure a is the larger of the two: */
    // 确保 a 大于 b
    if (size_a < size_b) {
        sign = -1;
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    else if (size_a == size_b) {
        /* Find highest digit where a and b differ: */
        // 找到最高位 a 与 b的差异
        i = size_a;
        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
            ;
        if (i < 0)
            return (PyLongObject *)PyLong_FromLong(0);
        if (a->ob_digit[i] < b->ob_digit[i]) {
            sign = -1;
            { PyLongObject *temp = a; a = b; b = temp; }
        }
        size_a = size_b = i+1;
    }
    z = _PyLong_New(size_a);
    if (z == NULL)
        return NULL;
    for (i = 0; i < size_b; ++i) {
        /* The following assumes unsigned arithmetic
           works module 2**N for some N>PyLong_SHIFT. */
        borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    for (; i < size_a; ++i) {
        borrow = a->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    assert(borrow == 0);
    if (sign < 0) {
        Py_SIZE(z) = -Py_SIZE(z);
    }
    return long_normalize(z);
}

与普通四则运算减法相同，数不够大则向高一位借位，
减法运算函数 x_sub 的示例图如下，注：PyLong_SHIFT 为 30

longobject x_sub

整数相乘

源文件：Objects/longobject.c

long_mul

k_mul 函数是一种快速乘法 源文件

Karatsuba 的算法主要是用于两个大数的乘法，极大提高了运算效率，相较于普通乘法降低了复杂度，并在其中运用了递归的思想。
基本的原理和做法是将位数很多的两个大数 x 和 y 分成位数较少的数，每个数都是原来 x 和 y 位数的一半。
这样处理之后，简化为做三次乘法，并附带少量的加法操作和移位操作。

具体可以看 wiki Karatsuba 算法的实现

其他

在 Objects/longobject.c
的第三行有这么一句话 XXX The functional organization of this file is terrible，
而且这个注释在Python2.7版本中也有，并一直保留到最新版本master分支，看来是一段陈年往事。