無限級数の計算を高速化する方法について簡単な質問があります。これは例の 1 つにすぎません: arctan(x) = x - x^3/3 + x^5/5 - x^7/7 + ....
大きな数を扱うことができるライブラリがあるとしましょう。最初の明白な解決策は、ターゲット N に到達するまで、シーケンスの各要素の加算/減算を開始することです。
X^n を事前に保存することもできるので、次の要素ごとに x^(n+2) を計算する代わりに lastX*(x^2) を実行できます。
しかし、全体としては非常にシーケンシャルなタスクのようで、複数のプロセッサ (8+) を利用するにはどうすればよいでしょうか??.
どうもありがとう！
編集: 100k から 1m の反復を計算する必要があります。これは C++ ベースのアプリケーションですが、抽象的な解決策を探しているので問題ありません。返信ありがとうございます。
問題を分解して、所有しているプロセッサまたはスレッドの数に一致させる必要があります。あなたの場合、たとえば、あるプロセッサが偶数項で動作し、別のプロセッサが奇数項で動作する可能性があります。x^2 を事前計算して lastX*(x^2) を使用する代わりに、lastX*(x^4) を使用して他のすべての項をスキップします。8 個のプロセッサを使用するには、前の項に x^16 を掛けて 8 個の項をスキップします。
PS ほとんどの場合、このような問題が発生した場合は、結果を計算するより効率的な方法を探す価値があります。ほとんどの場合、より優れたアルゴリズムはより多くの馬力を打ち負かします。
円周率の値を数百万桁まで計算しようとしている場合は、最初に、収束が速く、並列化に適した系列を選択することに細心の注意を払う必要があります。次に、十分な桁数がある場合は、それらを複数のプロセッサに分割することが最終的に費用対効果が高くなります。これを行うことができる bignum ライブラリを見つけるか、作成する必要があります。
さまざまな方法で変数を因数分解できることに注意してください。例えば：
atan(x)= x - x^3/3 + x^5/5 - x^7/7 + x^9/9 ...
= x*(1 - x^2*(1/3 - x^2*(1/5 - x^2*(1/7 - x^2*(1/9 ...
2 行目は最初の行の単純な実装よりも効率的ですが、後者の計算には、最初から最後まで依存関係の線形チェーンがあります。項をペアで組み合わせることで、並列性を向上させることができます。
= x*(1-x^2/3) + x^3*(1/5-x^2/7) + x^5*(1/9 ...
= x*( (1-x^2/3) + x^2*((1/5-x^2/7) + x^2*(1/9 ...
= [yet more recursive computation...]
ただし、各計算にかかる時間は、それを保持するために必要な精度に依存するため、この高速化は思っているほど単純ではありません。アルゴリズムを設計する際には、これを考慮する必要があります。また、あなたの代数は密接に関わっています。つまり、上記の場合、定数による除算を行うと無限に繰り返される分数が得られるため、何らかの方法でそれを処理する方法を見つける必要があります。
さて、この例では、シリーズを合計することができます (適切な場所に括弧がある場合):
(-1)^i * (x^(2i + 1))/(2i + 1)
次に、プロセッサ 1/8 で、i = 1、9、17、25、... の項の合計を計算します。
次に、プロセッサ 2/8 で、i = 2、11、18、26、... の項の合計を計算します。
など、最後に部分和を合計します。
または、あなたが (ほぼ) 提案したように、プロセッサ 1 に i = 1..16 (たとえば)、プロセッサ 2 に i = 17..32 などを与えることができます。前回のもの。シリーズに 8x16 を超える要素が必要な場合は、最初に各プロセッサにさらに割り当てます。
この例では、並列化する価値があるかどうかは疑問です。並列スレッドがまだ起動している間に、1 つのプロセッサで倍精度の精度が得られるのではないかと思います。しかし、これはこの例の単なる推測であり、おそらく並列化に努力する価値のある多くのシリーズを作成できます。
そして、@Mark Ransom がすでに述べたように、より優れたアルゴリズムは、ブルート フォースと多くのプロセッサを毎回打ち負かす必要があります。