n ** n ** n Pythonのヒューリスティック

Question

Pythonで遊んだだけで、興味深いものが見つかりました：コンピュータ（i5,3 GHz）は、数時間の計算を試みた後にちょうどハングアウトします10 ** 10 ** 10。 私は数学はPythonが作成された目的ではないことを知っていますが、Pythonを計算するための方法はありません。誰がどのように最も洗練された方法でn ** n ** nを解決するためのアイデアを持っていますn ** n ** n

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

---

1）を2倍高速に動作n ** (2** lg(n**n))：

は私の観察私がこれまで持っているのですか？

2）メモリ濫用を最小限に抑えるために、発電機で助けてもらえますか？

Answer 1

10 ** 10 ** 10は、非常に非常に多い数字である。 Pythonはその数を表すのに十分なメモリを割り当てようとしています。 10.000.000.000（100億）桁のメモリは、コンピュータが一度に提供できるものよりも多くのメモリを必要とするため、コンピュータは現在、メモリをディスクにスワップしてスペースを確保しています。

収まらないいくつかの番号にsys.getsizeof()を使用してみて、説明するために：

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

ので、追加の桁がおよそ 10倍より多くのメモリを必要とします。上記の金額はバイト単位であるため、100万桁の数字はほぼ半分メガバイト、1000万桁は4メガバイトを要します。 Extrapolitingでは、あなたの数は4ギガバイトのメモリを必要とします。 Pythonにそのような多くのメモリが与えられたとしても、あなたのOSとハードウェアによって異なります。

最近のプラットフォームでは、Pythonは整数をincrements of 30 bitsに格納します。したがって、30ビットごとに追加の4バイトのストレージが必要です。 (log2(10 ** 10 ** 10)/30 * 4)/(1024 ** 3) ==約4.125GiBになる100億桁については、

この大きな数値を表すために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