python - bignums 在内部是如何表示的？

Question

Python 提供了一种称为“long”的“bignum”类型，它可以表示任意大的数字。 这个类型的内部表示是什么？

我问的部分原因是我很好奇这些数字上哪些操作可能特别快或特别慢。例如，与乘法或除法相比，位移是否特别快(因为它适用于“常规”整数)？

Answer 1

CPython 的任意精度整数存储在二进制数字 数组中。每个 digit 由 15 位或 30 位组成。加法、减法和位移都是 O(n)。乘法(对于足够大的值)使用 Karatsuba multiplication这是 O(n**1.585)。除法仍然使用经典的O(n**2)算法。