n ** n ** n эвристика в Python

Question

Я просто играю с Python и нашел только что-то интересное: мой компьютер (i5, 3 ГГц) просто болтался после нескольких часов попыток вычислить 10 ** 10 ** 10. Я знаю, что Math не является целью для Python, но мне интересно, нет ли способа помочь Python, чтобы вычислить его.

То, что я до сих пор мое наблюдение: n ** (2** lg(n**n)) работает в 2 раза быстрее, чем n ** n ** n

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

---

1) Кто-нибудь есть идеи, как решить n ** n ** n в наиболее изощренным способом?

2) Могут ли генераторы помочь свести к минимуму злоупотребление памятью?

Answer 1

10 ** 10 ** 10очень очень много. Python пытается выделить достаточно памяти для представления этого числа. 10.000.000.000 (10 миллиардов) цифр занимает намного больше памяти, чем может обеспечить ваш компьютер за один раз, поэтому ваш компьютер теперь заменяет память на диск, чтобы освободить место, поэтому все становится так очень медленным.

Для иллюстрации, попробуйте использовать sys.getsizeof() на некоторые цифры, которые соответствуют:

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

так что дополнительная цифра требует примерно 10 раз больше памяти. Суммы, приведенные выше, составляют байты, поэтому 1 миллион цифр занимает почти половину мегабайта, 10 миллионов цифр - 4 мегабайта. Экстраполируя, ваш номер потребует 4 гигабайт памяти. Это зависит от вашей ОС и оборудования, если Python даже получит столько памяти.

Python хранит целые числа в increments of 30 bits на современных платформах; поэтому каждые 30 бит требуют дополнительных 4 байтов памяти. За 10 миллиардов цифр, которые сводятся к (log2(10 ** 10 ** 10)/30 * 4)/(1024 ** 3) == about 4.125GiB.

Вы не можете использовать Python для представления чисел, больших. даже не числа с плавающей точкой может достичь этой высокой:

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

Я не знаком с bignum (большое количество) обработки в Python; возможно, у gmpy libray есть возможности для представления таких чисел, которые лучше.

Answer 2

Если целочисленная точность не первостепенное значения, вы можете использовать float номер

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

Однако для больших значений те быстро достигают свои пределы:

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

Вы можете получить гораздо больше с 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') 

По умолчанию, даже те, которые не могут представлять 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 

Но эти ограничения не являются фиксированными.Использование getcontext() вы можете сделать их как большой, как вы хотите:

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

Но помните, что эти цифры не являются 100% точным до последней цифры (ваш компьютер, вероятно, даже не хватает памяти для магазина каждая цифра) , поэтому не удивляйтесь, если это произойдет:

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