您现在的位置是：首页>全部文章全部文章

python如何实现超长整数？

2020年11月26日 15:23【python】226人已围观

当您使用像C这样的低级语言进行编码时，您会担心为整数选择正确的数据类型和限定符。在每一步中，您都需要考虑int是否足够大，还是应该用long甚至更高的long double。但是在用python进行编码时，您不必担心这些“琐碎的”事情，因为python支持任意大小的整数。

在C语言中，当您尝试使用内置函数计算2^20000时，powl它将inf作为输出。

```C
#include <stdio.h>
#include <math.h>

int main(void) {
  printf("%Lf\n", powl(2, 20000));
  return 0;
}
```
```bash
$ gcc 1.c
$ ./a.out
inf
```
但是对于Python来说，这简直是小菜一碟
```python
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
... 6021 digits long ...
...
6309376
```
Python必须在内部做一些漂亮的事情来支持任意大小的整数，而今天我们发现了底层！

# 表示法和定义
Python中的整数在C中是这么定义的
```C
struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};
```
**PyObject_VAR_HEAD**是一个宏，扩展为**PyVarObject**  
它具有以下结构
```C
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
```
还有其他类型的**PyObject_VAR_HEAD**

+ PyBytesObject
+ PyTupleObject
+ PyListObject
这表明一个整数，就像元组或列表一样，其长度是可变的，这是我们首次了解它如何支持巨大的整数。_longobject宏展开后，大体上可视为
```c
struct _longobject {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
    digit ob_digit[1];
};
```
这些是PyObject结构中的一些meta字段，用于引用计数（垃圾收集），但是我们需要单独的文章。我们关注的字段ob_digit,在某种程度上是ob_size。

# 解码 ob_digit
**ob_digit**是一从unit32_t类型定义的，数字类型的数组，静态分配给长度1。因为它是一个数组，所以ob_digit主要是一个数字*，它是指向数字的指针，因此如果需要，可以将其分配为任何长度。这使得python可以表示和处理巨大的长整数。

通常，在像C这样的低级语言中，整数的精度限于64位，但是Python实现了任意精度的整数。从Python 3开始，所有整数都表示为一个bignum，并且这些整数仅受主机系统的可用内存限制。

# 解码 ob_size
ob_size保留ob_digit中的元素计数。为了在将内存分配给数组ob_digit时更加高效，python会过度配置，然后依靠ob_size的值来确定数组中实际容纳的元素数。

# 存储
一种简单的以整数方式存储整数的方法是，将一个十进制数字实际存储在数组的一个项目中，然后像小学数学一样执行加法和减法之类的操作。

通过这种方法，数字5238将存储为
![](/media/editor/71915727-5e03ed00-31a2-11ea-99c1-cdf28e74b595_20200117044440751555.png)

这种方法效率低下，因为我们将用完32位数字（uint32_t）来存储实际上仅从0到9的十进制数字，并且本来可以很容易地用4位表示，并且在编写像python这样通用的东西时，核心开发人员必须比这更有资源。

那么，我们可以做得更好吗？当然，否则，本文不应在Internet上占有一席之地。让我们深入研究python如何存储超长整数。

# pythonic方式
Python不会在数组ob_digit的每个项目中仅存储一个十进制数字，而是将数字从10转换为2^30，然后将每个元素都调用为0到2^30-1之间的数字。

在十六进制系统中，基数为16〜2^4，这意味着十六进制数字的每个“数字”范围为十进制的0到15之间。类似地，对于Python，“数字”是在基体2^30，这意味着它的取值范围在0到2^30 - 1 = 1073741823十进制范围内。

这样，python可以有效地使用几乎所有分配的空间（每个数字32位），并保持自身的资源丰富性，并且仍可以像小学数学一样执行诸如加法和减法之类的运算。

根据平台的不同，Python使用具有30位数字的32位无符号整数数组或具有15位数字的16位无符号整数数组。它需要几个位来执行操作，这些操作将在以后的文章中进行讨论。

### 示例：1152921504606846976
如前所述，一个用于Python的“数字”是基地2^30，因此，如果将1152921504606846976转换为基数2^30你将得到100

1152921504606846976 = 1 *（2^30)^2 + 0 *（2^30)^1 + 0 *（2^30)^0

由于先ob_digit保留最低有效数字，因此它将以3个不同的数字存储为001。

此值的_longobject结构将保留

+ ob_size 为 3
+ ob_digit 为 [0, 0, 1]
![1152921504606846976以pythonic方式表示](/media/editor/72000622-b5b95b80-3269-11ea-9e76-1755cd648f0d_20200117045526314284.png)

我创建了一个演示REPL，它将输出Python内部存储整数的方式，并且还引用了诸如ob_size，ob_refcount等的结构成员。

# 对超长整数的运算
现在，我们对python如何支持和实现任意精度整数有了一个清晰的认识，现在该花时间了解如何对它们进行各种数学运算了。

# 加法
整数以“数字方式”持久存在，这意味着加法就像我们在小学时所学的一样简单，而python的源代码向我们展示了这也是它的实现方式。 longobject.c文件中名为x_add的函数执行两个数字的加法运算。
```C
...
    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;
...
```
上面的代码片段来自x_add函数，您可以看到它在数字上进行迭代，并按位执行加法运算，并计算和传播进位。

当加法的结果为负数时，事情变得很有趣。 ob_size的符号是整数的符号，这意味着，如果您使用负数，则ob_size将为负数。 ob_size的绝对值将确定ob_digit中的位数。

# 减法
类似于加法的实现方式，减法也以数字方式发生。 longobject.c文件中名为x_sub的函数执行两个数字的减法。
```C
...
    for (i = 0; i < size_b; ++i) {
        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 */
    }
...
```
上面的代码片段来自x_sub函数，您可以看到它如何遍历数字并执行减法运算以及计算和传播挖洞。确实与加法非常相似。

# 乘法
同样，幼稚的实现乘法的方法将是我们在小学数学中学到的，但是效率不是很高。为了保持效率，Python实施了Karatsuba算法，该算法在O（n^log2^3）基本步骤中将两个n位数字相乘。

该算法稍微复杂，不在本文的讨论范围之内，但是您可以在longobject.c文件的k_mul和 k_lopside_mul函数中找到其实现。

# 除法及其他操作
所有对整数的操作都在longobject.c文件中定义，查找和跟踪每个整数都非常简单。警告：详细了解每一个过程都需要一些时间，因此在开始浏览之前先抢些爆米花。

# 常用整数的优化
Python 在-5到256范围内预分配了小整数。这种分配发生在初始化期间，并且由于我们无法更新整数（不变性），因此这些预分配的整数是单例，并且直接引用而不是重新分配。这意味着每次我们使用/创建一个小整数时，python而不是重新分配只是返回预分配的引用。

可以在宏IS_SMALL_INT和longobject.c中的函数get_small_int中跟踪此优化。 这样，python为常用的整数节省了大量空间和计算量。

上一篇：安装jupyter并设置为后台服务

下一篇：使用ctypes优化Python代码