Come vengono rappresentati i bignum internamente?

Question

Python fornisce un tipo "bignum" chiamato "long" che può rappresentare numeri arbitrariamente grandi. Qual è la rappresentazione interna di questo tipo?

Chiedo in parte perché sono curioso di sapere quali operazioni potrebbero essere particolarmente veloci o lente su questi numeri. Ad esempio, il bit shifting è particolarmente veloce rispetto alla moltiplicazione o alla divisione (come per gli "regolari" ints)?

Answer 1

Gli interi di precisione arbitrari di CPython sono memorizzati in una serie di binari digits. Ogni digit consiste di 15 o 30 bit. Addizione, sottrazione e spostamento dei bit sono tutti O (n). La moltiplicazione (per valori sufficientemente grandi) utilizza Karatsuba multiplication che è O (n ** 1.585). La divisione utilizza ancora l'algoritmo O (n ** 2) classico.

Answer 2

Bene, ho scritto questo. Non sono sicuro di quanto sia bello, ma puoi usarlo come punto di partenza per un benchmark più raffinato e completo.

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 

Quello che sto vedendo è che int() operazioni sono davvero più veloce, ma non molto più veloce.