N ** n ** n heuristic in Python

Question

I just communicate with Python and found only an interesting thing: my computer (i5, 3 GHz) just freezes after several hours trying to calculate 10 ** 10 ** 10 . I know that Math is not a goal for Python, but I wonder if there is no way to help Python calculate it.

So far, I have been observing my observation: n ** (2** lg(n**n)) works 2 times faster than 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 most difficult way?

2) Can generators help minimize memory abuse?

Answer 1

10 ** 10 ** 10 very large number . Python is trying to allocate enough memory to represent this number. 10,000,000,000 (10 billion) digits takes up much more memory than your computer can provide at one time, so your computer now replaces the memory with a disk to free up space, so things get so very slow.

To illustrate, try using sys.getsizeof() for some numbers that match:

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

therefore, an extra digit requires about 10 times more memory. The amounts given above are bytes, so 1 million digits takes up almost half a megabyte, 10 million digits - 4 megabytes. By extrapolating, your number will require 4 gigabytes of memory. It depends on your OS and hardware, if Python even gets so much memory.

Python stores integers in 30-bit increments on modern platforms; therefore, every 30 bits require an additional 4 bytes of memory. For 10 billion digits, which boils down to (log2(10 ** 10 ** 10) / 30 * 4) / (1024 ** 3) == about 4.125GiB.

You cannot use Python to represent large numbers. Even floating point numbers cannot reach this maximum:

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

I am not familiar with bignum (large number) handling in Python; perhaps gmpy libray has the ability to represent numbers that are better.

Answer 2

If integer precision doesn't really matter, you can use float numbers

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

However, for large values, they will quickly reach their limits:

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

You can get much higher 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') 

By default, even those that cannot represent 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 

But these restrictions are not fixed. Using getcontext() , you can make them as large as you want:

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

But remember that these numbers are not 100% accurate to the last digit (your computer probably does not even have enough memory to store each digit), so do not be surprised if this happens:

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