Comment les bignums sont-ils représentés en interne?

Question

Python fournit un type "bignum" appelé "long" qui peut représenter des nombres arbitrairement grands. Quelle est la représentation interne de ce type?

Je demande en partie parce que je suis curieux de savoir ce que les opérations pourraient être particulièrement rapide ou lent sur ces chiffres. Par exemple, le décalage de bits est-il particulièrement rapide comparé à la multiplication ou à la division (comme c'est le cas pour les entiers "réguliers")?

Answer 1

entiers de précision arbitraire de CPython sont stockés un ensemble de digits binaire. Chaque digit se compose de 15 ou 30 bits. L'addition, la soustraction et les décalages de bits sont tous O (n). La multiplication (pour les valeurs suffisamment grandes) utilise Karatsuba multiplication qui est O (n ** 1.585). Division utilise toujours l'algorithme classique O (n ** 2).

Answer 2

Eh bien, j'ai écrit ceci. Je ne suis pas sûr à quel point c'est bon, mais vous pouvez l'utiliser comme point de départ pour un benchmark plus raffiné et complet.

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 

Ce que je vois est que int() opérations sont en effet plus rapide, mais pas beaucoup plus vite.