bignums如何代表內部？

Question

Python提供了一個名爲「long」的「bignum」類型，它可以表示任意大的數字。 這種類型的內部表示是什麼？

我問一部分是因爲我很好奇哪些操作可能在這些數字上特別快或慢。例如，與乘法或除法相比，位移特別快（因爲它是「常規」整數）？

Answer 1

CPython的任意精度整數存儲在二進制數組digits中。每個digit由15位或30位組成。加法，減法和位移都是O（n）。乘法（對於足夠大的值）使用Karatsuba multiplication，它是O（n ** 1.585）。 分部仍然使用經典的O（n ** 2）算法。

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()操作的確是更快，但不是很多更快。