無限シリーズの並列計算

Question

無限シリーズの計算をスピードアップする方法について、簡単な質問があります。これは例の1つにすぎません。arctan（x）= x -x^3/3 + x^5/5 -x^7/7 + ....

大きな数字で作業できるライブラリがあるとしましょう。最初に明らかな解決策は、ターゲットNに到達するまでシーケンスの各要素の追加/減算を開始/減算することです。

また、x^（n+2）を計算する代わりに次の要素ごとにx^nを事前に保存することもできます。lastx*（x^2）を実行できます

しかし、それは非常に順番に順番にタスクであるように思われ、複数のプロセッサ（8+）を利用するために何ができますか？

どうもありがとう！

編集：100K〜1Mの反復を計算する必要があります。これはC ++ベースのアプリケーションですが、抽象的なソリューションを探しているので、それは問題ではありません。返信ありがとうございます。

Answer 1

あなたが持っているプロセッサまたはスレッドの数に合わせて問題を打ち破る必要があります。あなたの場合、たとえば、1つのプロセッサが均等な用語で作業し、別のプロセッサが奇妙な用語で作業することができます。 x^2を事前に計算してlastx*（x^2）を使用する代わりに、lastx*（x^4）を使用して他のすべての用語をスキップします。 8つのプロセッサを使用するには、前の用語にx^16を掛けて8つの用語をスキップします。

PSこのような問題が提示された場合、ほとんどの場合、結果を計算するより効率的な方法を探すことは価値があります。より良いアルゴリズムは、ほとんどの場合、より多くの馬力を打ち負かします。

Answer 2

Piの値を何百万もの場所などに計算しようとしている場合は、まず、迅速に収束するシリーズを選択し、並列化に適しているシリーズを選択することに細心の注意を払いたいと考えています。その後、十分な数字がある場合、最終的には複数のプロセッサに分割するのが費用対効果が高くなります。これを行うことができる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番目の行は、1行目の素朴な実装よりも効率的ですが、後者の計算には、最初から最後まで依存関係の線形チェーンがあります。ペアで用語を組み合わせることで、視差を改善できます。

       = 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...]

ただし、各計算で取られた時間はそれを保持するために必要な精度に依存するため、このスピードアップはあなたが思うほど単純ではありません。アルゴリズムを設計する際には、これを考慮する必要があります。また、あなたの代数は密接に関与しています。つまり、上記の場合、一定の数字で定期的な分裂を行うと、無限に繰り返される分数が得られるため、何らかの方法で対処する方法を見つける必要があります。

Answer 3

さて、この例では、シリーズを合計することができます（適切な場所にブラケットがある場合）：

(-1)^i * (x^(2i + 1))/(2i + 1)

次に、プロセッサ1の8でi = 1、9、17、25、...の項の合計を計算します。

次に、プロセッサ2の8でi = 2、11、18、26の項の合計を計算します。

など、最終的に部分的な合計を追加します。

または、（ほぼ）提案するように、i = 1..16（たとえば）プロセッサ1に、i = 17..32にプロセッサ2に与えることができ、xの各連続したパワーを次のように計算できます。前回のもの。シリーズに8x16を超える要素が必要な場合は、そもそも各プロセッサにさらに割り当てます。

この例では、まったく並行する価値があるかどうかは疑わしいですが、パラレルスレッドがまだ目覚めている間に、1プロセッサで2倍の精度の精度に到達すると疑っています。しかし、それはこの例の推測にすぎません。おそらく、並列化が努力する価値がある多くのシリーズができます。

そして、@Mark Ransomがすでに言っているように、より良いアルゴリズムは毎回Brute-Forceと多くのプロセッサを打ち負かすべきです。