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

Question

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

我之所以问这个问题，部分原因是我想知道在这些数字上哪些操作可能特别快或特别慢。例如，相比乘法或除法，位移是否特别快速（就像“常规”整数一样）？

- nibot

---

请参考以下链接：http://stackoverflow.com/a/870429/297323 - Fredrik Pihl

我们在谈论哪个版本的Python？在Python2中，有int和long，但在Python3中，只有long（重命名为int）。这是Python2 int的实现方式。 - Two-Bit Alchemist

@Two-BitAlchemist 版本有关系吗？据我所知，实现方式在很长一段时间内基本保持不变。无论如何，我们正在谈论的是任意精度的实现，因此不是 Python 2 int。 - user395760

你可以阅读 longintrepr.h。 - jfs

http://legacy.python.org/dev/peps/pep-0237/ - M4rtini

Answer 1

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

- casevh

Answer 2

好的，这是我写的。我不确定这有多好，但你可以把它作为更精细和完整基准测试的起点。

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() 操作确实更快，但并不是非常快。

- salezica