11

補間関数の 2 つの実装を次に示します。引数u1は常に ~ の間0.です1.

#include <stdio.h>

double interpol_64(double u1, double u2, double u3)
{ 
  return u2 * (1.0 - u1) + u1 * u3;  
}

double interpol_80(double u1, double u2, double u3)
{ 
  return u2 * (1.0 - (long double)u1) + u1 * (long double)u3;  
}

int main()
{
  double y64,y80,u1,u2,u3;
  u1 = 0.025;
  u2 = 0.195;
  u3 = 0.195;
  y64 = interpol_64(u1, u2, u3);
  y80 = interpol_80(u1, u2, u3);
  printf("u2: %a\ny64:%a\ny80:%a\n", u2, y64, y80);
}

80 ビットlong doubles を使用する厳密な IEEE 754 プラットフォームでは、 のすべての計算はinterpol_64()IEEE 754 の倍精度に従って行われinterpol_80()、80 ビットの拡張精度で行われます。プログラムは次を出力します。

u2: 0x1.8f5c28f5c28f6p-3
y64:0x1.8f5c28f5c28f5p-3
y80:0x1.8f5c28f5c28f6p-3

「関数が返す結果は常に と の間」という性質に興味がありu2ますu3interpol_64()上記の値が示すように、このプロパティは の false ですmain()

プロパティが真である可能性はありますinterpol_80()か? そうでない場合、反例は何ですか?u2 != u3それらの間に最小距離があることを知っていれば役に立ちますか? プロパティが真であることが保証される中間計算の仮数幅を決定する方法はありますか?

編集:私が試したすべてのランダム値で、中間計算が内部的に拡張精度で行われたときに保持されたプロパティ。interpol_80()引数を取る場合long double、反例を構築するのは比較的簡単ですが、ここでの質問は特にdouble引数を取る関数に関するものです。これにより、反例があったとしても、その反例を構築することがはるかに難しくなります。


注: x87 命令を生成するコンパイラは、 と に対して同じコードを生成する可能性がありますinterpol_64()interpol_80()、これは私の質問に接しています。

4

2 に答える 2

3

はい、interpol_80() は安全です。デモを行いましょう。

問題は、入力が64ビット浮動小数点数であることを示しています

rnd64(ui) = ui

結果は正確です(*と+が数学演算であると仮定)

r = u2*(1-u1)+(u1*u3)

64 ビット float に丸められた最適な戻り値は

r64 = rnd64(r)

これらのプロパティがあるので

u2 <= r <= u3

保証されている

rnd64(u2) <= rnd64(r) <= rnd64(u3)
u2 <= r64 <= u3

u1,u2,u3 の 80bit への変換も正確です。

rnd80(ui)=ui

ここで、 を仮定0 <= u2 <= u3して、不正確な float 演算を実行すると、最大で 4 つの丸め誤差が発生します。

rf = rnd(rnd(u2*rnd(1-u1)) + rnd(u1*u3))

最も近い偶数に丸めると仮定すると、これは正確な値から最大で 2 ULP になります。丸めが 64 ビット浮動小数点または 80 ビット浮動小数点で実行される場合:

r - 2 ulp64(r) <= rf64 <= r + 2 ulp64(r)
r - 2 ulp80(r) <= rf80 <= r + 2 ulp80(r)

rf64は 2 ulp ずれる可能性があるため、interpol-64() は安全ではありませんが、どうrnd64( rf80 )ですか?
次のことがわかります。

rnd64(r - 2 ulp80(r)) <= rnd64(rf80) <= rnd64(r + 2 ulp80(r))

以来0 <= u2 <= u3

ulp80(u2) <= ulp80(r) <= ulp80(r3)
rnd64(u2 - 2 ulp80(u2)) <= rnd64(r - 2 ulp80(r)) <= rnd64(rf80)
rnd64(u3 + 2 ulp80(u3)) >= rnd64(r + 2 ulp80(r)) >= rnd64(rf80)

幸いなことに、範囲内のすべての数値と同様に(u2-ulp64(u2)/2 , u2+ulp64(u2)/2)

rnd64(u2 - 2 ulp80(u2)) = u2
rnd64(u3 + 2 ulp80(u3)) = u3

以来ulp80(x)=ulp62(x)/2^(64-53)

このようにして証明を得る

u2 <= rnd64(rf80) <= u3

u2 <= u3 <= 0 の場合、同じ証明を簡単に適用できます。

調査する最後のケースは、u2 <= 0 <= u3 です。2 つの大きな値を減算すると、結果は ulp(big-big)/2 ではなく、ulp(big)/2 オフになる可能性があり
ます。

r - 2 ulp64(r) <= rf64 <= r + 2 ulp64(r)

幸いなことにu2 <= u2*(1-u1) <= 0 <= u1*u3 <= u3、これは丸めた後も保持されます

u2 <= rnd(u2*rnd(1-u1)) <= 0 <= rnd(u1*u3) <= u3

したがって、追加された量は反対の符号であるため、次のようになります。

u2 <= rnd(u2*rnd(1-u1)) + rnd(u1*u3) <= u3

丸めた後も同様です。

u2 <= rnd64( rf80 ) <= u3

QED

完全にするには、非正規化入力 (段階的なアンダーフロー) に注意する必要がありますが、ストレス テストでそれほど悪質にならないことを願っています。それらがどうなるかは説明しません...

編集

次のアサーションは少し概算であり、0 <= u2 <= u3 の場合にいくつかのコメントが生成されたため、フォローアップを次に示します。

r - 2 ulp80(r) <= rf80 <= r + 2 ulp80(r)

次の不等式を書くことができます。

rnd(1-u1) <= 1
rnd(1-u1) <= 1-u1+ulp(1)/4
u2*rnd(1-u1) <= u2 <= r
u2*rnd(1-u1) <= u2*(1-u1)+u2*ulp(1)/4
u2*ulp(1) < 2*ulp(u2) <= 2*ulp(r)
u2*rnd(1-u1) < u2*(1-u1)+ulp(r)/2

次の丸め操作では、

ulp(u2*rnd(1-u1)) <= ulp(r)
rnd(u2*rnd(1-u1)) < u2*(1-u1)+ulp(r)/2 + ulp(u2*rnd(1-u1))/2
rnd(u2*rnd(1-u1)) < u2*(1-u1)+ulp(r)/2 + ulp(r)/2
rnd(u2*rnd(1-u1)) < u2*(1-u1)+ulp(r)

合計の 2 番目の部分については、次のようになります。

u1*u3 <= r
rnd(u1*u3) <= u1*u3 + ulp(u1*u3)/2
rnd(u1*u3) <= u1*u3 + ulp(r)/2

rnd(u2*rnd(1-u1))+rnd(u1*u3) < u2*(1-u1)+u1*u3 + 3*ulp(r)/2
rnd(rnd(u2*rnd(1-u1))+rnd(u1*u3)) < r + 3*ulp(r)/2 + ulp(r+3*ulp(r)/2)/2
ulp(r+3*ulp(r)/2) <= 2*ulp(r)
rnd(rnd(u2*rnd(1-u1))+rnd(u1*u3)) < r + 5*ulp(r)/2

私は元の主張を証明しませんでしたが、そこまでではありません...

于 2012-12-05T21:24:55.813 に答える
2

の精度低下の主な原因はinterpol_64乗算です。2 つの 53 ビットの仮数を掛けると、105 ビットまたは 106 ビット (上位ビットが運ぶかどうかによる) の仮数が得られます。これは大きすぎて 80 ビットの拡張精度値に収まらないため、一般に、80 ビット バージョンでも精度が失われます。それがいつ起こるかを正確に定量化することは非常に困難です。最も簡単に言えることは、丸め誤差が蓄積したときに発生するということです。2 つの項を追加するときに小さな丸めステップもあることに注意してください。

ほとんどの人は、おそらく次のような関数でこの問題を解決するでしょう:

double interpol_64(double u1, double u2, double u3)
{ 
  return u2 + u1 * (u3 - u2);
}

しかし、より良い実装ではなく、丸めの問題についての洞察を探しているようです。

于 2012-12-05T15:24:05.727 に答える