2

浮動小数点の倍精度値xを 12 (正しく丸められた) 有効数字の 10 進数に変換しようとしています。x10 ^ 110 と 10 ^ 111 の間にあり、10 進表現が の形式になると想定していx.xxxxxxxxxxxE110ます。そして、楽しみのために、浮動小数点演算のみを使用しようとしています。

すべての演算が倍精度演算である以下の疑似コードにたどり着きました。表記1e98は、数学的な 10^98 に1e98_2最も近い double であり、数学的な減算 10^98- の結果に最も近い double1e98です。表記は、オペランド、、fmadd(X * Y + Z)を使用した融合乗算加算演算用です。XYZ

  y = x * 2^-1074;    // exact
  q = y / 1e98;       // q is denormal and the significand of q interpreted
                      // as an integer is our candidate for the 12 decimal
                      // digits of x

  r = fmadd(q * 1e98 - y);  // close to 1e98 * (error made during the division)

  // If 1e98_2 >= 0, we divided by a number that was smaller than we wished
  // The correct answer may be q or q+1.

  if (r and 1e98_2 have opposite signs)
  {
    return the significand of q;
  }

  s = copysign(2^-1074, r);
  r1 = abs(r);
  r2 = abs(1e98_2);

  h = 1e98 * 0.5 * 2^-1074;

  Set rounding mode to downwards

  r3 = fmadd(r2 * q + r1);

  if (r3 < h)
  {
    return the significand of q;
  }
  else
  {
    return significand of (q + s)
  }

上記の疑似コードに混乱が広がっていることをお詫びしますが、まだあまり明確ではないため、次の質問があります。

  1. 最初の fmadd は (1e98 * (除算中に発生したエラー) を計算するために) 意図したとおりに機能しますか?

  2. しるし。彼らが正しいと自分に言い聞かせることはできません。しかし、私は彼らが間違っていると自分自身に納得させることもできません.

  3. このアルゴリズムが間違った結果を生成する可能性がある頻度についての考え、おそらく議論はありますか?

  4. まったく機能する場合、「q = y / 1e98」を「q = y * 1e-98」に変更しても(他のすべての命令は同じままにして)、アルゴリズムが引き続き機能する可能性はありますか?

このアルゴリズムはテストしていません。fmadd命令を備えたコンピューターはありませんが、上記を実行できるコンピューターを見つけたいと思っています。

4

1 に答える 1

2

を正確y/dな演算とし、q=rnd(y/d)最も近い浮動小数点数に丸めた結果を とします。
次に、真の誤差に d を掛ける と、rt=(rnd(y/d)-y/d)*d=q*d-yfmadd で実行した演算は(+/- 1) であり、エラーがであるため、最初に消失していることを意味します。r=rnd(q*d-y)
q*d-yq*d<nbits(q)+nbits(d)yq*d|rt|<0.5*ulp(q)*dnbits(q)

だからq*1e98 - y = r、どこで|r|*2^1074 <= 0.5e98 < 5*10^98(2番目の不等式はラッキーです)

q*(10^98) - y = r + (10^98-1e98)*qここで|10^98-1e98|*q*2^1074 <= 0.5e95(少なくとも 15 桁の精度を想定log(2^53)/log(10) > 15)

だからあなたは尋ねます|q*(10^98)-y|*2^1074>5*10^97

近似値は次の|q*(10^98)-y|とおりです。r+1e98_2*q

なので|r| < 5*10^98、 と|r+(10^98-1e98)*q|<|r|符号が反対なら、質問 2 に肯定的に答えると思います。

r1e98_2が同じ符号を持っている場合、 を超える可能性があるため、 vs5*10^97の議論によるさらなる処理r3 = 1e98_2*q + rh=0.5e98*2^-1074

質問 3 については、一見したところ、次の 2 つのことがアルゴリズムを失敗させる可能性があると言えます。

  • 1e98_2正確ではありません (10^98-1e98-1e98_2 = -3.6e63およそ)

  • 上で見たように、少し小さいだけでhはありません。ht=0.5*10^98*2^-1074

真の誤差r3tはおおよそです(1e98_2-3e63)*q + r < r3(1e98_2>0 であるため、>0 の場合のみが興味深い)。

そのため、真のエラー r3t が真のタイ ht を下回っているときに、近似タイ h を超えるエラー r3 の近似は、不正確な丸めにつながる可能性があります。可能であれば、質問 3 はどのくらいの頻度で行われますか?

上記の不等リスクを軽減するために、r3 の大きさを切り捨てようとしたため、r3 <= 1e98_2*q + r. エラー境界の真の分析を実行するのに少し疲れました...

So I scanned for an error, and the first failing example I found was 1.0000000001835e110 (I assume correctly rounded to nearest double, but it is in fact 1000000000183.49999984153799821120915424942630528225695526491963291846957919215885146546696544423465444842668032e98).

この場合、r1e98_2は同じ符号であり、

  • (x/1e98) > 1000000000183.50000215

  • qしたがって、仮数は次のように丸められます。1000000000184

  • r3>h(r3*2^1074約 5.000001584620017e97) でありq+s、 であるべきところを誤ってインクリメントしましたがq-s間違いなくバグです。

私の答えは次のとおりです。

  1. はい、r=fmadd(q * 1e98 - y)正確に 1e98* (除算中に発生したエラー) ですが、除算は気にしません。推測を提供するだけです。重要なのは、減算が正確であるということです。

  2. |r| < 5*10^98はい、 、および|r+(10^98-1e98)*q|<|r|符号が反対の場合、符号は正しいです。しかし、1e98_2 が < 0 であるかどうかはわかりません。

  3. 最初の失敗例を(1.0000000001835e110 - 1.0e110)/1.0e110 ulp -> 1.099632e6取り上げると、非常に単純な推測では、100 万回に 1 回、r3 が h を超えているということになります。したがって、q+s が qs に修正されると、r3>hwhileの発生r3t<htは 1/いずれにせよ1,000,000...関心のある範囲には10 ^ 15倍以上があるので、これは深刻な答えではないと考えてください...

  4. はい、上記の議論は、それが生成された方法とは関係なく、推測 q についてのみであり、1. の減算は依然として正確です...

于 2014-02-14T04:43:15.883 に答える