n**n**n heuristics in Python

Question

I just play around with Python and found just interesting thing: my computer (i5, 3 GHz) just hang out after several hours of attempting to compute 10 ** 10 ** 10. I know Math isn't a purpose Python was created for, but I wonder isn't there a way to help Python to compute it.

What I have so far is my observation: n ** (2** lg(n**n)) works 2 times faster then n ** n ** n

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

---

1) Does anyone have an idea how to solve n ** n ** n in a most sophisticated way?

2) Do generators can help in order to minimize memory abuse?

Answer 1

10 ** 10 ** 10 is a very very large number. Python is trying to allocate enough memory to represent that number. 10.000.000.000 (10 billion) digits takes a lot more memory than your computer can provide in one go, so your computer is now swapping out memory to disk to make space, which is why things are now so very very slow.

To illustrate, try using sys.getsizeof() on some numbers that do fit:

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

so an additional digit requires roughly 10 times more memory. The amounts above are in bytes, so a 1 million digit number takes almost half a megabyte, 10 million digits takes 4 megabytes. Extrapoliting, your number would require 4 gigabytes of memory. It depends on your OS and hardware if Python will even be given that much memory.

Python stores integers in increments of 30 bits on modern platforms; so every 30 bits requires an additional 4 bytes of storage. For 10 billion digits that comes down to (log2(10 ** 10 ** 10) / 30 * 4) / (1024 ** 3) == about 4.125GiB.

You can't use Python to represent numbers this large. Not even floating point numbers can reach that high:

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

I'm not that familiar with bignum (big number) handling in Python; perhaps the gmpy libray has facilities to represent such numbers that are better.