Unit of Last Place (ULP) の定義について

On the definition of ulp(x) という論文を読んだメモです。

浮動小数点数の誤差を議論するとき、最終桁の重み (Unit of Last Place, ULP) が単位として使われます。 例えば、以下のような使い方をします。

  • 最近接丸めをした場合、その丸め誤差は0.5ULP以下になる
  • 方向丸め（切り捨てや切り上げ、零への丸めなど）を行った場合、その丸め誤差は1.0ULP未満になる

しかし、以下の倍精度二進浮動小数点数の例を考えてみると、丸め方によってULPの定義が変わるようでは困ることがわかります。

  • 0x1.fffffffffffff8p+0を2.0に丸めた場合、丸め誤差は2^-53、2.0の最終桁の重みは2^-51なので、丸め誤差は0.25ULP（？）
  • 0x1.fffffffffffff8p+0を0x1.fffffffffffffp+0に丸めた場合、丸め誤差は2^-53、0x1.fffffffffffffの最終桁の重みは2^-52なので、丸め誤差は0.5ULP（？）

したがって、「丸める前の値」のみに基づいてULPが定義されるべきであることがわかります。 しかし、「丸める前の値」は浮動小数点数ではないので、「最終桁の重み」というのを正しく定義することができません。 というわけで、やはり困ってしまいます。

そういう場合にも適応できるULPの定義は、下のようなものが挙げられます。

  1. 「丸める前の値」を挟む二つの浮動小数点数の距離を1ULPとする
  2. 「丸める前の値」に最も近い二つの浮動小数点数の距離を1ULPとする

1.の定義は、以下の欠点を抱えています。

  • 「丸める前の値」がちょうど浮動小数点数で表せる場合に困る
    • 実際に困るのは、基数のべき乗ぴったりの時
  • 挟む二つの浮動小数点数の片方が±∞の時に困る

2.の定義は、実数の全領域で矛盾なく定義できるという利点がありますが、基数のべき乗に近いところで「最も近い二つの浮動小数点数」が「丸める前の値」を挟まない（両方とも「丸める前の値」よりも絶対値が小さい）ことがあり、やや直観に反します。

1.の定義と2.の定義は、浮動小数点数で表せるほとんどの領域上で同じ定義となりますが、オーバーフロー付近、アンダーフロー付近、基数のべき乗をわずかに超えた付近のみで異なる定義となります。 浮動小数点数をオーバーフロー付近やアンダーフロー付近で使うべきではないですが、基数のべき乗をわずかに超えた付近は使わざるを得ないことがあります。 よって、以下では基数のべき乗をわずかに超えた付近での問題を議論します。

基数のべき乗を超えた付近で定義が異なるというのは、例えば真の値が0x1.00000000000003p+0で倍精度二進浮動小数点数に丸める場合を考えてみるとわかります。

  • 真の値を挟む二つの浮動小数点数は、0x1.0000000000000p+0と0x1.0000000000001p+0なので、1.の定義では1ULP=2^-52
  • 真の値に最も近い二つの浮動小数点数は、0x1.fffffffffffffp-1と0x1.0000000000000p+0なので、2.の定義では1ULP=2^-53

1.の定義では、基数のべき乗のところでULPの大きさが変わりますが、2.の定義では、基数のべき乗を少し超えた付近でULPの大きさが変わります。

この切り替わる点は r^N x_{cut}と表せます。倍精度二進浮動小数点数の場合、1.の定義では r=2, x_{cut}=1、2.の定義では r=2, x_{cut}=1+2^{-54}=0x1.0000000000004p+0となります。

これを一般化すると、浮動小数点数の基数をr、仮数部はp桁*1だとして、

  • 1.の定義の場合、 x_{cut} = 1
  • 2.の定義の場合、 x_{cut} = 1 + \frac{r -1}2 r^{-p}

となります。

ところで、ULPの定義にこだわる理由は、「丸め誤差がxxULP以内だから、○○な性質を持つ浮動小数点数に丸められているはず」「○○な性質を持つ浮動小数点数に丸めたから、丸め誤差がxxULP以内のはず」という議論をしたいからです。 以下では、これらの性質が成り立つかを議論します。

丸め誤差が0.5ULP未満だから、唯一の最も近い浮動小数点数に丸めたはず

1 + \left(\frac{r}{2}-1\right)r^{-p} \le x_{cut}を満たしていれば、上の性質が成り立ちます。

  • 二進浮動小数点数であれば、1.の定義でも2.の定義でも条件を満たすため、上の性質が成り立ちます（1.の定義はぎりぎりです）。
  • 三以上の基数の場合、2.の定義の場合のみ上の性質が成り立ちます。

最も近い浮動小数点数（のうちの一つ）に丸めたのだから、丸め誤差が0.5ULP以下のはず

x_{cut} \le 1 + \frac 1 2 r^{-p}を満たしていれば、上の性質が成り立ちます。

  • 二進浮動小数点数であれば、1.の定義でも2.の定義でも条件を満たすため、上の性質が成り立ちます（2.の定義はぎりぎりです）。
  • 三以上の基数の場合、1.の定義の場合のみ上の性質が成り立ちます。

なお、三進浮動小数点数であっても、 x_{cut} = \frac 1 2 3^{-p}とすれば、上の二つの性質を満たすULP関数を作ることができます。 四進以上の場合、上の二つの性質を同時に満たすULP関数を作ることは不可能です。

切り上げで丸めても切り捨てで丸めても、丸め誤差は1.0ULP未満のはず

  • 基数がいくつであっても、1.の定義の場合のみ上の性質が成り立ちます。

丸め誤差が1.0ULP未満なら、切り上げで丸めた数か切り捨てで丸めた数のはず

1.の定義の場合、成り立ちません。基数のべき乗をちょっと超えた数から1.0ULP未満の浮動小数点数は、r+1個あります。 2.の定義なら成り立つ気がしますが、記載されていませんでした。

結論

1.の定義がわかりやすく*2、二進浮動小数点数の場合には求められるすべての性質を満たすためこれを選ぶべきです。

ただし、無限大付近で問題になるため、絶対値が最大の浮動小数点数より大きい範囲では、2.の定義を流用するのが簡単です。 IEEE754で「こういう場合に無限大に丸めるべき」と定められたとおりに丸めれば、「最近接丸めを行った場合、その丸められた値が有限であれば、丸め誤差は0.5ULP以下」の性質は満たします。

*1:ケチ表現を使う二進浮動小数点数の場合、その1bitを含みます。倍精度二進浮動小数点数なら53桁と数えます。

*2:2.の定義の場合、「実数xを浮動小数点数に最近接丸めで丸めた場合のULPでみた丸め誤差」という関数が不連続になって取り扱いが不便です。