如何在内部代表bignums？

Question

Python提供了一个名为"long"的"bignum"类型,它可以代表任意大的数字. 这种类型的内部表示是什么？

我问的部分是因为我很好奇这些数字的操作可能特别快或慢.例如,与乘法或除法相比,位移特别快(因为它是"常规"整数)？

Answer 1

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