您现在的位置是:首页>全部文章全部文章 python如何实现超长整数? 2021年2月26日 09:53【python】316人已围观 当您使用像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将存储为  这种方法效率低下,因为我们将用完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]  我创建了一个演示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代码 相关文章 理解Python中的yield 使用ctypes优化Python代码 通过无损压缩减少NumPy内存使用 python海象运算符":="的三种用法 Python的 5 种高级用法,效率提升没毛病! Python中"is"和"=="的区别 工厂模式之Python实现 单例模式之Python实现 python多行注释规范 使用Python识别验证码 文章评论 共有316条评论来说两句吧... 用户名: 阅读排行 使用Python识别验证码 python如何实现超长整数? Django DTL常用过滤器 python多行注释规范 通过无损压缩减少NumPy内存使用 工厂模式之Python实现 Python中"is"和"=="的区别 python海象运算符":="的三种用法 1.两数之和 Python的 5 种高级用法,效率提升没毛病! 站长推荐 Django DTL常用过滤器 标签云 公告 python 验证码 Django DTL 过滤器 算法 LeetCode 规范 注释 设计模式 Linux Apache Numpy jupyter ctypes 站点信息 文章统计:16条 文章评论:2条 点赞统计: 24个 统计数据:百度统计 微信公众号:扫描二维码,关注我们 站点地图:SiteMap