大整数是如何在内部表示的？

Question

Python 提供了一种叫做 "long" 的大数类型，可以表示任意大的数字。 这种类型在内部是怎么表示的呢？

我之所以问这个问题，是因为我想知道在这些数字上，哪些操作可能特别快或者特别慢。例如，位移操作相比于乘法或除法，速度是不是特别快（就像在“普通”整数中那样）？

Answer 1

我写了这个。虽然我不太确定这个效果怎么样，但你可以把它当作一个起点，去做一个更完善、更完整的基准测试。

import timeit

def timef(f, *args):
    return timeit.timeit(lambda: f(*args), number = 1000000) # repetitions


tests = {
    'addition'      : lambda x: x + 17,
    'substraction'  : lambda x: x - 17,
    'multiplication': lambda x: x * 17,
    'division'      : lambda x: x / 17,
    'float division': lambda x: x / 17.0
}


for name, f in tests.items():
    print  'int {0}'.format(name).ljust(20), timef(f, 0)
    print 'long {0}'.format(name).ljust(20), timef(f, 10 ** 50)
    print

我发现，int()这个操作确实更快，但并不是快很多。

Answer 2

CPython中的任意精度整数是以一个二进制的数字数组来存储的。每个数字由15位或30位二进制位组成。加法、减法和位移操作的复杂度都是O(n)，也就是说它们的计算时间会随着数字的大小线性增长。当数字足够大的时候，乘法会使用一种叫做Karatsuba乘法的方法，这种方法的复杂度是O(n**1.585)，比普通的乘法快一些。至于除法，仍然使用传统的O(n**2)算法，也就是计算时间会随着数字的大小平方增长。