n ** n ** n euristica in Python

Question

Mi limito a giocare con Python e ho trovato solo una cosa interessante: il mio computer (i5, 3 GHz) si blocca dopo diverse ore di tentativi di calcolare 10 ** 10 ** 10. So che la matematica non è uno scopo per cui Python è stato creato, ma mi chiedo se non ci sia un modo per aiutare lo Python a calcolarlo.

Quello che ho finora è la mia osservazione: n ** (2** lg(n**n)) funziona 2 volte più veloce n ** n ** n

n = 8 ** (8 ** 8) 
n2 = 8 ** (2 ** 24) 
# measured by timeit 
> 4.449993866728619e-07 
> 1.8300124793313444e-07 

---

1) Qualcuno ha un'idea di come risolvere n ** n ** n in un modo più sofisticato?

2) I generatori possono aiutare a minimizzare l'abuso di memoria?

Answer 1

10 ** 10 ** 10 è un numero molto grande . Python sta tentando di allocare memoria sufficiente a rappresentare quel numero. 10.000.000.000 (10 miliardi) di cifre richiedono molta più memoria di quella che il tuo computer può fornire in una volta sola, quindi il tuo computer sta ora scambiando la memoria su disco per creare spazio, motivo per cui le cose ora sono così molto lente.

Per illustrare, provare a utilizzare sys.getsizeof() su alcuni numeri che si adattano:

>>> import sys 
>>> sys.getsizeof(10 ** 10 ** 6) 
442948 
>>> sys.getsizeof(10 ** 10 ** 7) 
4429264 

così una cifra aggiuntiva richiede circa 10 volte più memoria. Gli importi di cui sopra sono espressi in byte, quindi un numero di 1 milione di cifre richiede quasi mezzo megabyte, 10 milioni di cifre richiedono 4 megabyte. Estrapolando, il tuo numero richiederebbe 4 gigabyte di memoria. Dipende dal tuo sistema operativo e hardware se a Python verrà assegnata molta memoria.

Python memorizza numeri interi in increments of 30 bits su piattaforme moderne; quindi ogni 30 bit richiede ulteriori 4 byte di spazio. Per 10 miliardi di cifre che scende a (log2(10 ** 10 ** 10)/30 * 4)/(1024 ** 3) == su 4.125GiB.

Non è possibile utilizzare Python per rappresentare numeri così grandi. Nemmeno numeri in virgola mobile può raggiungere così in alto:

>>> 10.0 ** 10 ** 10 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
OverflowError: (34, 'Result too large') 

Io non sono che la familiarità con bignum (grande numero) di movimentazione in Python; forse lo gmpy libray ha le strutture per rappresentare tali numeri che sono migliori.

Answer 2

Se la precisione intero non è della massima importanza, è possibile utilizzare float numeri

>>> 3**3**3 
7625597484987 
>>> 3.**3.**3. 
7625597484987.0 

Tuttavia, per valori più grandi quelli raggiungerà presto i loro limiti:

>>> 5.**5.**5. 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
OverflowError: (34, 'Numerical result out of range') 

si può ottenere molto più alto con decimal:

>>> import decimal 
>>> d = decimal.Decimal 
>>> d(5)**d(5)**d(5) 
Decimal('1.911012597945477520356404560E+2184') 
>>> d(10)**d(10)**d(8) 
Decimal('1.000000000000000000000000000E+100000000') 

Per impostazione predefinita, anche quelli che non può rappresentare 10**10**10:

>>> d(10)**d(10)**d(10) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "/usr/lib/python2.7/decimal.py", line 2386, in __pow__ 
    ans = ans._fix(context) 
    File "/usr/lib/python2.7/decimal.py", line 1676, in _fix 
    ans = context._raise_error(Overflow, 'above Emax', self._sign) 
    File "/usr/lib/python2.7/decimal.py", line 3872, in _raise_error 
    raise error(explanation) 
decimal.Overflow: above Emax 

Ma questi limiti non sono fissi.Utilizzando getcontext() si può renderli grande come si desidera:

>>> decimal.getcontext().Emax = 1000000000000 
>>> d(10)**d(10)**d(10) 
Decimal('1.000000000000000000000000000E+10000000000') 

Ma ricordate che quei numeri non sono al 100% precisi per l'ultima cifra (il computer probabilmente non ha nemmeno di memoria sufficiente per negozio ogni cifra) , quindi non essere sorpreso se questo accade:

>>> d(10)**d(10)**d(10) == d(10)**d(10)**d(10) + 1000000 
True