c - より良い平均を示す方法は?

Question

Al Kelley/Ira Pohl によるA Book On C(3rd Edition) のPage 60-61 に関する質問は次のとおりです。

次のコード フラグメントは、移動平均を計算する 2 つの異なる方法を示しています。

int i;
double x;
double avg= sum= 0.0;
double navg;

for (i=1; scanf("%lf", &x)==1; ++i)
{
  avg+= (x-avg)/i;
  sum+= x;
  navg= sum/i;
}

本に書かれている元の質問は次のとおりです。「通常の」数値を入力すると、 avg と navg は同じように見えます。合計がオーバーフローしない場合でも、平均が優れていることを実験的に示します。

初心者プログラマーとしての私の質問は次のとおりです。

1. 「より良い」アルゴリズムの基準は何ですか? 精度と実行時間の 2 つが重要な要素だと思いますが、アルゴリズムを「より良く」するものは他にありますか?

2. 精度と実行時間に関して、オーバーフローが除外された場合でも、avg が navg よりも優れた方法であることを実験的に証明するにはどうすればよいでしょうか? 大きさが大きく異なるなど、「通常とは異なる」数値を使用する必要がありますか?

Answer 1

++i を実行しても、 for() ループでゼロで除算していることに注意してください

Answer 2

あまりうまく表現されていませんが、これは有効な質問だと思います。問題は、風鈴が言及した質問でさえ、うまく表現されておらず、良い回答を得る前に閉じられたことです。

ただし、質問自体は、特に本に含まれていることを示すクローズドな質問にとって興味深いものであるため、より多くの人々を何らかの方向に導く可能性があります.

どちらのアルゴリズムも特に優れているとは思いません。単純な平均では、精度が失われるように見えます。または、いくつかの大きさの差がある数値を平均すると、数値が失われることさえありますが、おそらく他のアルゴリズムでも同じことが発見される可能性があります。入力データのセットが異なるだけです。

したがって、特に既存の本からのものであるため、これは適切な回答を求める完全に有効な質問だと思います。

例を挙げて、2 つのアルゴリズムについて私が考えていることを隠そうとします。ほぼ同じ大きさの 4 つの数値があり、それらを平均したいとします。

素朴な方法では、最初にそれらを次々に合計します。最初の 2 つを合計すると、明らかに下限で 1 ビットの精度が失われます (おそらく、指数が 1 つ大きくなったためです)。最後の数値を追加すると、2 ビットが失われます (このビットは現在、合計の上位部分を表すために使用されています)。しかし、次に 4 で割ります。この場合、本質的には、指数から 2 を引くだけです。

この過程で私たちは何を失いましたか？これで、最初にすべての数値が 2 ビット切り捨てられた場合の答えが簡単になります。この場合、明らかに、結果として得られる平均の端数の最後の 2 ビットはゼロになり、さらに 2 ビット相当のエラーが発生する可能性があります (切り捨てられたすべてのビットがたまたま元の数値の 1 である場合と比較して、ゼロ）。基本的に、ソースが 23 ビットの小数部を持つ単精度浮動小数点数である場合、結果の avg は約 19 ビット相当の精度を持つことになります。

合計された最初の数値はそれほど精度を失うことはありませんでしたが、単純な方法からの実際の結果はより優れています。

各反復の微分法では、適切に重み付けされた差が合計に追加されます。数値が同じ大きさである場合、この差はおそらく 1 桁下のどこかになります。次に、現在のカウントで除算されます。この操作では何も失われませんが、最後の数値 (この例では i=4) の結果の差は、ソース数値よりも約 3 桁小さい場合があります。これを、元の数値とほぼ同じ大きさの移動平均に追加します。

したがって、この例の微分法では、最後の数値を追加すると、約 3 ビットの精度が失われたように見えます。4 つの数値すべてについて、本質的に精度が失われた 5 ビットにまで下がっているように見えることさえあります。方法？

微分法は従うのが難しいです。おそらく、私の仮定に誤りがありました。しかし、それは明らかだと思います。どちらか一方のパフォーマンスが優れていると見なすのは妥当ではないようです。そうであれば、データのレイアウトと大きさの違いに依存している可能性があります。