n ** n ** n heurystyki w Pythonie

Question

Po prostu bawię się z Python i znalazłem po prostu interesującą rzecz: mój komputer (i5, 3 GHz) po prostu spędzać wolny czas po kilku godzinach próby obliczenia 10 ** 10 ** 10. Wiem, Matematyka nie jest celem Python został stworzony dla, ale zastanawiam się, nie ma sposobu, aby pomóc Python do obliczenia go.

Co mam tak daleko jest moja obserwacja: n ** (2** lg(n**n)) pracuje 2 razy szybciej niż n ** n ** n

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

---

1) Czy ktoś ma pomysł jak rozwiązać n ** n ** n w najbardziej wyrafinowany sposób?

2) Czy generatory mogą pomóc w zminimalizowaniu nadużyć pamięci?

Answer 1

10 ** 10 ** 10 to bardzo bardzo duża liczba. Python próbuje przydzielić wystarczającą ilość pamięci do reprezentowania tej liczby. 10.000.000.000 (10 miliardów) cyfr zajmuje o wiele więcej pamięci niż komputer może dostarczyć za jednym razem, więc twój komputer wymienia teraz pamięć na dysk, aby zrobić miejsce, dlatego rzeczy są teraz bardzo, bardzo powolne.

Aby zilustrować, spróbuj użyć sys.getsizeof() na niektóre numery, które pasują:

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

więc dodatkowa cyfra wymaga około 10 razy więcej pamięci. Powyższe kwoty są w bajtach, więc milion cyfr zajmuje prawie pół megabajta, a 10 milionów cyfr zajmuje 4 megabajty. Ekstrapolacja, twój numer wymagałby 4 gigabajtów pamięci. Zależy to od systemu operacyjnego i sprzętu, jeśli Python otrzyma nawet tyle pamięci.

Python przechowuje liczby całkowite w increments of 30 bits na nowoczesnych platformach; więc co 30 bitów wymaga dodatkowych 4 bajtów pamięci. Za 10 miliardów cyfr sprowadza się do (log2(10 ** 10 ** 10)/30 * 4)/(1024 ** 3) == około 4,125 GiB.

Nie można używać języka Python do reprezentowania tak dużych liczb. Nawet liczb zmiennoprzecinkowych, że może osiągnąć wysokie:

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

nie jestem zaznajomiony z bignum (duża liczba) postępowanie w Pythonie; być może gmpy libray ma urządzenia do reprezentowania takich liczb, które są lepsze.

Answer 2

Jeśli całkowita precyzja nie jest sprawą najwyższej wagi, można użyć float numery

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

Jednakże dla większych wartości te będą szybko osiągnąć swoje granice:

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

można uzyskać znacznie wyższe ze 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') 

Domyślnie, nawet tych, którzy nie mogą reprezentować 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 

Ale te granice nie są stałe.Korzystanie getcontext() można uczynić je tak duża, jak chcesz:

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

Należy jednak pamiętać, że te liczby nie są w 100% dokładne do ostatniej cyfry (komputer prawdopodobnie nawet nie ma wystarczającej ilości pamięci do sklepie każda cyfra) , więc nie zdziw się, jeśli tak się stanie:

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