0

a、b は 32 ビット浮動小数点値、N は 32 ビット整数、k は 0、1、2、... M の値を取ることができます。c_k = a + ( N + k ) * b を計算する必要があります。演算は 32 ビット演算 (倍精度ではない) である必要があります。問題は正確さです。次のうちどれがより正確ですか?:

I) c_k = a + ( N + k ) * b

II) 最初​​に計算します: c_0 = a + N * b
次に、加算によって c_1、c_2 などを繰り返し計算します:
c_1 = c_0 + b;
c_2 = c_1 + b;

4

2 に答える 2

3

連鎖加算は、実行できる最悪の演算の 1 つです。最後の結果の丸め誤差は、連鎖内の各加算の単一演算の丸め誤差の正味合計になるためです。最初の方法を使用するか、 を使用する方が正確c_i = c_0 + b*iです。

于 2013-05-17T16:22:17.390 に答える
2

操作の数を気にしていないように見えるので、IEEE 754 モデルを想定すると、32 ビット操作で正確に実行できます。
Shewchuck Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometry Predicates - http://www.cs.berkeley.edu/~jrs/papers/robustr.pdfまたはhttp://www-2.cs.cmu.edu/afsを参照してください。 /cs/project/quake/public/papers/robust-arithmetic.ps

2つの正確な操作を定義します（論文を参照）

(product,residue) = twoproduct(a,b)
(sum,residue) = twosum(a,b)

次に、N+k を 2 つの 24 ビット仮数に分解する必要があります。たとえば、

NkH = (N+k) / 256;
NkL = (N+K) % 256;

次に、潜在的に不正確な乗算が 2 つあります。

( HH , HL ) = twoproduct( NkH , b)
( LH , LL ) = twoproduct( NkL , b)

次に、これらを合計できます ( HH , HL ) + ( LH , LL ) + a

これは、高速拡張合計で正確に実行できます（論文をもう一度参照してください）

(c1,c2,c3,c4,c5) = sort_increasing_magnitude(HH,HL,LH,LL,a)
(s2,s1) = twosum( c2,c1 )
(s3,s2) = twosum( c3,s2 )
(s4,s3) = twosum( c4,s3 )
(s5,s4) = twosum( c5,s4 )

次に、操作が無限精度の算術演算で実行されたかのように、s5 で正確に丸められた結果を取得します。

于 2013-05-16T20:45:21.697 に答える