8

これは、ウィキペディアのカハンの加算アルゴリズムです。

function KahanSum(input)
    var sum = 0.0
    var c = 0.0
    for i = 1 to input.length do
        y = input[i] - c    // why subtraction?
        t = sum + y
        c = (t - sum) - y
        sum = t
    return sum

（加算ではなく）減算を使用する特定の理由はありますか？の計算でオペランドを入れ替えた場合、c代わりに加算を使用できますか？どういうわけか、それは私にとってより理にかなっているでしょう：

function KahanSum(input)
    var sum = 0.0
    var c = 0.0
    for i = 1 to input.length do
        y = input[i] + c    // addition instead of subtraction
        t = sum + y
        c = y - (t - sum)   // swapped operands
        sum = t
    return sum

それとも、私がまだ知らない浮動小数点の加算と減算の間に奇妙な違いがありますか？

また、元のアルゴリズム(t - sum) - yとの間に違いはありますか？とにかく、左結合であるt - sum - yため、括弧は冗長ではありませんか？-

4

2 に答える 2

2

私の知る限り、あなたの方法はウィキペディアのものとまったく同じです。唯一の違いは、-の符号c、したがってその意味-が逆になっていることです。ウィキペディアのアルゴリズムでcは、は合計の「間違った」部分です。c = 0.0001は、合計が本来より少し大きいことを意味します。あなたのバージョンでcは、は合計に対する「修正」です。c = -0.0001は、合計を少し小さくする必要があることを意味します。

かっこは読みやすさのためだと思います。それらは私たちのためのものであり、機械ではありません。

于 2011-12-09T14:38:58.430 に答える
2

2つのアルゴリズムは同等です。実行中の唯一の違いは、の符号ですc。加算を使用する理由は、Kahanのバージョンでcは、エラーを表すためです。これは、通常、正しい値から計算値を引いたものです。

括弧は操作の順序を指定するという意味で、括弧は絶対に必要です。実際、これらがこのアルゴリズムを機能させるものです。

ほとんどの言語でそうであるように、減算が左結合である場合、2つは同じであるとa - b - c評価されます。(a - b) - cしかし、カハンアルゴリズムの減算はであり、それはとして評価されるa - (b - c)べきではありませんa - b + c。

浮動小数点の加算と減算は結合法則ではありません。標準の算術演算で同等の式の場合、操作を実行する順序によって異なる結果が得られる場合があります。

わかりやすくするために、小数点以下3桁の精度で作業してみましょう。これは、4桁の結果が得られた場合、それを丸める必要があることを意味します。次に、いくつかの特定の値について(a - b) - c数学的に同等のものと比較します。a - (b + c)

(998 - 997) - 5 = 1 - 5 = -4

と

998 - (997 + 5) = 998 - Round(1002)
                = 998 - 1000 = -2

したがって、2番目のアプローチは精度が低くなります。

Kahanアルゴリズムでtはsum、通常、に比べて比較的大きくなりyます。そのため、上記の例のように、正しい順序で操作を行わないと、結果の精度が低下することがよくあります。

于 2011-12-09T15:15:11.070 に答える