起步

在以前的python2中,整型分为int和long,也就是整型和长整型, 长整型不存在溢出问题, 即可以存放任意大小的数值. 因此在python3 中,统一使用长整型.

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    long_dealloc,                               /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    long_to_decimal_string,                     /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

这是整型类型完整的元信息

举个栗子看看源码中如何比较两个整型对象的大小:

static PyObject * long_richcompare(PyObject *self, PyObject *other, int op)
{
    int result;
    PyObject *v;
    CHECK_BINOP(self, other);
    if (self == other)
        result = 0;
    else
        result = long_compare((PyLongObject*)self, (PyLongObject*)other);
    ...
}

具体实现在 long_compare 中:

static int long_compare(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t sign;

    if (Py_SIZE(a) != Py_SIZE(b)) {
        sign = Py_SIZE(a) - Py_SIZE(b);
    }
    else {
        Py_ssize_t i = Py_ABS(Py_SIZE(a));
        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
            ;
        if (i < 0)
            sign = 0;
        else {
            sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
            if (Py_SIZE(a) < 0)
                sign = -sign;
        }
    }
    return sign < 0 ? -1 : sign > 0 ? 1 : 0;
}

长整型在python内部是用一个int数组(ob_digit[n])保存值的. 待存储的数值的低位信息放于低位下标, 高位信息放于高下标.比如要保存 123456789 很长,但我们的int只能保存3位(假设):

ob_digit[0] = 789;
ob_digit[1] = 456;
ob_digit[2] = 123;

结构大致是这样的, 最低位的789存在0索引, 而正负符号信息由ob_size保存, 像上面的例子中对象元素个数是3, 那么ob_size = 3 而如果表示数是负数的, 那么 ob_size = -3.

就是将整数保存在一个数组里,加减就是从低位起，在相对应的位作加减,并将多余的进位或不足的补位.除法和小学计算方式一样. 乘法比较麻烦, python里用的是 Karatsuba 算法.后面具体看看它的实现代码.

作为数值对象,它的相关操作在 long_as_number :

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    ...
};

确定了一个整型对象, 其规定的所有操作都要一一实现,我们可以看看加法操作是如何实现的:

static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b); // 操作检查

    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        // 如果是小整型, 使用更为简单的运算
        PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
                                          MEDIUM_VALUE(b));
        return result;
    }
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0) {
            // 两个加数都是负数时, 当正数相加后, 加在负号, 和初中学的规则一样
            z = x_add(a, b);
            if (z != NULL) {
                assert(Py_REFCNT(z) == 1);
                Py_SIZE(z) = -(Py_SIZE(z));
            }
        }
        else
            z = x_sub(b, a);// 类似 -4 + 9 变成 9 - 4 来运算
    }
    else {
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b);
        else
            z = x_add(a, b);
    }
    return (PyObject *)z;
}

在 x_add(a, b) 和 x_sub(a, b) 中, a,b两数都是当整数来运算的, long_add 更具数的正负和操作来决定调用哪个函数.

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;

    // 确保a是两个加数中较大的一个
    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);  // 申请一个能容纳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;                 // 移除低15位
    }
    for (; i < size_a; ++i) {                   // 处理a中高位数字
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
    return long_normalize(z);                   // 整理元素个数
}

PyLong_MASK的值是:

#define PyLong_SHIFT  15
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 1))

也就是 0b111111111111111 , 在长整型的ob_digit中元素理论上可以保存的int类型有32位. 但python中只保存15位, 这是有原因的, 因为这个两个数的乘积可以只用int来保存即可. carry 作为结果顺带进位处理. 和小学我们数字计算一样

计算结果保存在变量z中,但变量申请里a_size + 1的空间, 有时候并不是所有空间都用到, 所以需要进行整理 long_normalize(z):

static PyLongObject * long_normalize(PyLongObject *v)
{
    Py_ssize_t j = Py_ABS(Py_SIZE(v));
    Py_ssize_t i = j;

    // 从高位开始找,知道不是0为止
    while (i > 0 && v->ob_digit[i-1] == 0)
        --i;
    if (i != j)
        Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
    return v;
}

重新将ob_size调整至正确的数量.

乘法运算

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;
}

当两个数的乘积值能用long long类型保存是, 进行简单的两数相乘, 后用 PyLong_FromLongLong((long long)v) 进行调整. 整数过大则是调用 k_mul 进行计算, 这个函数是Karatsuba multiplication（一种比较高效的乘法算法）, 普通乘法的复杂度是n2，而Karatsuba算法的复杂度仅为3nlog3≈3n1.585, 它的原理是将大数分成两段较小的数, 通过3次乘法和部分位移和加法来做.

x = x_1 * 10^m + x_0

y = y_1 * 10^m + y_0

那么:

xy = (x_1 * 10^m + x_0) (y_1 * 10^m + y_0)

令:

z_2 = x_1 * y_1

z_1 = x_1 * y_0 + x_0 * y_1

z_0 = x_0 * y_0

于是就有

xy = z_2 * 10^2m + z_1 * 10^m + z_0

而z1的计算显然又要算两个乘法, 而其实它可以用z0和z2来表示:

z_1 = (x_1 + x_0) * (y_1 + y_0) - z_2 - z_0

这样z1用一次乘法和加减法可以获得.

言归正传, 在long_mul中具体的计算乘法规则在k_mul 中:

static PyLongObject * k_mul(PyLongObject *a, PyLongObject *b)
{
    // code...
    /* Use gradeschool math when either number is too small. */
    i = a == b ? 140 : 70;
    if (asize <= i) {
        if (asize == 0)
            return (PyLongObject *)PyLong_FromLong(0);
        else
            return x_mul(a, b);
    }
    
    // code...


}

当整数的需要在70位以下元素保存时, 采用x_mul的乘法方案, 这种方案直译就是小学乘法, 哈哈哈, 也就是模拟乘法竖式, 过程就不用我说了.

当位数很少的时候，Python用更快的朴素乘法. 至于更大的数为什么使用“复杂度更高”的 Karatsuba Multiplication 而不是O(nlogn)的FFT就不清楚了.

小整数

>>> a = 99
>>> b = 99
>>> id(a)
9318176
>>> id(b)
9318176
>>> a = 300
>>> b = 300
>>> id(a)
139991055746320
>>> id(b)
139991055746288
>>>

为什么99的id一样,而300的不一样呢?
在python中 -5~256 视为小整数, 为了避免不停的申请和释放, python会预先初始化所有的小整数对象, 在我们使用小整数的时候,其实没有创建,只是得到一个本来就在内存中的小整数对象的引用.

这个小整数和大整数之间的分界线用户是可以自己调整的, 当然是通过修改源码重新编译了.

在 longobject.c 超过5500行的代码中,有个不起眼的变量 small_ints ,就是保存小整数, 也就是小整数对象池:

static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

// NSMALLNEGINTS 是 5
// NSMALLPOSINTS 是 257

因此默认区间是[-5, 256).对象池的初始化在 int _PyLong_Init(void) 函数中,有兴趣的可以看一下.