ループ計算の再帰関係が非常に長くかかる

Question

Q(x)=[Q(x−1)+Q(x−2)]^2 
Q(0)=0, Q(1)=1 

Q（29）を見つける必要があります。私はPythonでコードを書いたが、それは時間がかかりすぎている。どのように出力を得る（どの言語でも問題ありません）？無限大になる傾向等比数列の種類があるので、これは、あまりにも長くかかります

a=0 
b=1 
for i in range(28): 
    c=(a+b)*(a+b) 
    a=b 
    b=c 
print(b) 

Answer 1

：ここ

は、私が書いたコードです。

例：

a=0 

b=1 

c=1*1 = 1 

a=1 

b=1 

c=2*2 = 4 

a=1 

b=4 

c=5*5 = 25 

a=4 

b=25 

c= 29*29 = 841 

a=25 

b=841 

. 
. 
. 

Answer 2

あなたは、もしCの％10 == 0をチェックし、それを分割し、時間の終了multiplyit番号にあなたはそれを分けたが、最終的に、それは同じ大規模になるだろうことができます数。この計算を本当に行う必要があるのであれば、C++を使って試してみてください。Pythonより速く実行するべきです。

---

ここではC++

#include <cstdlib> 
#include <iostream> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    long long int a=0; 
    long long int b=1; 
    long long int c=0; 
    for(int i=0;i<28;i++){ 
      c=(a+b)*(a+b); 
      a=b; 
      b=c; 
    } 

    cout << c; 
    return 0; 
} 

Answer 3

の中に書かれたコードは、私は、これはプログラミングで扱いやすい問題があるとは思わないのです。あなたのコードが遅い理由は、内部の数字が非常にと急成長するため、pythonは無限精度の整数を使用するため、結果を計算する時間がかかります。

倍精度の浮動小数点数で、あなたのコードを試してみてください。

は

a=0.0 
b=1.0 
for i in range(28): 
    c=(a+b)*(a+b) 
    a=b 
    b=c 
print(b) 

答えはinfです。これは、答えが最大表現可能な倍精度数値であるrougly 10^308よりはるかに大きいためです。有限精度の整数を試してみることもできますが、それらは表現可能な最大値がさらに小さくなります。倍精度を使用すると精度が低下することに注意してください。しかし、確かにあなたのhuuuge番号のすべての桁を知りたくはありません（副注：I happen to know that you do、あなたの仕事をさらに困難にします）。

だからここに私の懐疑論のためのいくつかの数学の背景です：あなたが解決できる場合

P[k] = sqrt(Q[k]) 
P[k] = P[k-2]^2 + P[k-1]^2 

：あなたの漸化式が

Q[k] = (Q[k-2] + Q[k-1])^2 

を行くあなたは、このシーケンスの平方根から、より扱いやすいシーケンスを策定することができますPの場合は、Q = P^2が表示されます。今

、このシーケンスを考えてみます。

R[k] = R[k-1]^2 

は同じ初期値から開始し、これは常に

P[k] = P[k-2]^2 + P[k-1]^2 >= P[k-1]^2 

（これは「かなり近い」となりますから、P[k]より小さくなります第1項の下限は第2項と比較して常に重要ではない）。、値2と

R[k] = R[k-1]^2 = R[k-2]^4 = R[k-3]^6 = R[k-m]^(2^m) = R[0]^(2^k) 

P[1 give or take]以降開始すると、私たちはP[k]の下限として

R[k] = 2^(2^k) 

を検討すべきで与えるか、これはk=28について2の数の指数を取る：私たちは、この配列を構築することができますsquarはPの最終値、のための少なくとも80807124桁だ

P[28] > 2^(2^28) = 2^(268435456) = 10^(log10(2)*2^28) ~ 10^80807124 

あなたが探している番号の根。つまり、Q[28]は10^1.6e8より大きくなります。その番号をテキストファイルに印刷すると、150メガバイト以上かかることになります。

これらの整数を正確に処理しようとしているとすれば、時間がかかる理由と、なぜアプローチを再考すべきかを理解できます。あなたはその膨大な数を計算することができますか？あなたはそれで何をしますか？あなたのスクリーンにその数字を印刷するのにどれくらいの時間がかかりますか？これは決して簡単なことではないので、紙面で問題を解決しようとしたり、その問題を回避しようとすることをお勧めします。

---

あなたはあなたの問題があるいかに難しいかの感覚を得るためにpythonで、このようなsympyシンボリック数学パッケージを使用できることに注意してください：

import sympy as sym 
a,b,c,b0 = sym.symbols('a,b,c,b0') 
a = 0 
b = b0 
for k in range(28): 
    c = (a+b)**2 
    a = b 
    b = c 
print(c) 

これはしばらく時間がかかるだろうが、それはあなたを記入します画面ではQ[k]の明示的な式がb0のみをパラメーターとしています。正確な結果を得るためには、そのモンスターにあなたの値を代入する必要があります。また式の上にsym.simplifyを試すこともできますが、意味のある何かを返すのを待つことができませんでした。

---

私はあなたのループを実行して終了しました。結果はそうk=28のための私の下限は、おそらく指数のオフによって-1のエラーに、少し大きい

>>> import math 
>>> print(math.log10(c)) 
49287457.71120789 

を持っています。この整数を格納するために必要なメモリは、約20 MBである

>>> import sys 
>>> sys.getsizeof(c) 
21830612 

です。

Answer 4

これはブルートフォースで解決することができますが、2つの異なる「遅い」操作を使用し、正しいアプローチを選択する際にトレードオフがあるため、依然として興味深い問題です。

PythonのネイティブPython実装の速度が遅い場所は2つあります。大きな数字の乗算と大きな数字の文字列への変換です。

Pythonは乗算にKaratsubaアルゴリズムを使用します。実行時間はO（n^1.585）で、nは数値の長さです。数値が大きくなると遅くなりますが、Q（29）を計算できます。

Pythonの整数を10進表現に変換するアルゴリズムは、はるかに低速です。実行時間はO（n^2）です。多数の場合、乗算よりもはるかに遅いです。

注：文字列への変換には実際の計算時間も含まれます。

私のコンピュータでは、Q（25）の計算には約2.5秒かかりますが、文字列への変換には約3分9秒が必要です。コンピューティングQ（26）には〜7.5秒が必要ですが、文字列への変換には〜12分36秒が必要です。数字のサイズが2倍になると、乗算時間は3倍に増加し、文字列変換の実行時間は4倍に増加します。文字列への変換の実行時間が支配的です。 Q（29）の計算には約3分20秒かかりますが、文字列への変換には12時間以上かかることがあります（実際にはそれほど長く待たなかった）。

非常に高速なGMPライブラリにアクセスできるgmpy2モジュールが1つあります。 gmpy2では、Q（26）は〜0.2秒で計算され、約1.2秒で文字列に変換されます。 Q（29）は〜1.7秒で計算でき、〜15秒で文字列に変換できます。 GMPにおける乗算はO（n * ln（n））です。 10進数への変換は、PythonのO（n^2）アルゴリズムより高速ですが、まだ乗算よりも遅いです。

最も速いオプションは、Pythonのdecimalモジュールです。 radix-2またはバイナリの内部表現を使用する代わりに、radix-10（実際には10の累乗）の内部表現を使用します。計算はやや遅くなりますが、文字列への変換は非常に高速です。それはちょうどO（n）です。 Q（29）の計算には〜9.2秒が必要ですが、計算と変換を一緒に行うには〜9.5秒しかかかりません。文字列に変換する時間はわずか0.3秒です。

decimalを使用したプログラム例です。また、最終値の個々の桁を合計します。

import decimal 

decimal.getcontext().prec = 200000000 
decimal.getcontext().Emax = 200000000 
decimal.getcontext().Emin = -200000000 

def sum_of_digits(x): 
    return sum(map(int, (t for t in str(x)))) 

a = decimal.Decimal(0) 
b = decimal.Decimal(1) 
for i in range(28): 
    c = (a + b) * (a + b) 
    a = b 
    b = c 


temp = str(b) 
print(i, len(temp), sum_of_digits(temp)) 

私は、何百万という数字を文字列に変換して上記の説明に追加する時間は含んでいませんでした。その時間は各バージョンで同じでなければなりません。