小清水 (@curekoshimizu) です。

昨日は 数学カフェ に初めて参加させていただき、

機械学習について刺激を受けました！

その中で、

コイン投げは確率界の Hello World というフレーズを聞いて

なるほどなるほど！と感じました。

そして、

そういえば丸め誤差界の Hello World はなんだろう？

と思い記事を書いてみました。

そもそも、 丸め誤差界 は業界というには狭すぎて、

そもそも丸め誤差に関する定理を聞く人も多いのでは？とも思います。

また、丸め誤差に関する本も少ないことなどから、

このセレクトがなるほど！となるかもわかりませんが、

私の主観で選択しました。

私的に思う、

丸め誤差界の Hello World はこちらになります！

「Sterbenzの定理」

この Sterbenz の定理、ゴールドバーグ先生の

what every computer scientist should know about floating-point arithmetic

の Theorem 11 にも載っていますので 皆さんもちろん知っていますよね！

とは言いつつも紹介します！

丸め誤差界の Hello World – Sterbenz の定理

Sterbenzの定理
$\beta$ 進浮動小数点環境とする。(2進でなくても構わない)
$x, y$ が有限値をとる浮動小数点数であり、 $\dfrac{y}{2} \leq x \leq 2y$ を満たすならば、 $x - y$ の結果を、丸め誤差なく正しく $\beta$ 進浮動小数点数として表現可能。

この定理は 有限値をとる浮動小数点数 という過程しかなく、

正規化数 という数以外にも、 非正規化数 というクラスにも成立することを言っています。

この点でかなり広いです。

この 正規化数・非正規化数 については、

後半の 「Prop. の証明 – 整数を用いた $\beta$ 進 $p$ 桁の浮動小数点数の表示」の章 に概略を記載しましたのでご参考ください。

どこに Hello World 性があるの？

浮動小数点の丸め誤差理論は、

誤差を抑えたり評価したりということをする理論だと思います。

その理論としては、

誤差なく計算できる！ という誤差のない究極性！があり、

なおかつ証明が極めて簡単！というところに Hello World 性があると思います。

Sterbenz の定理の証明

(証明)

$\dfrac{y}{2} \leq x \leq 2y$

であるから、 $x, y$ は同符号であることがわかる。

対称性から $x , y \geq 0$ で証明できればよい。

また、

$\dfrac{y}{2} \leq x \leq 2y$

から

$\dfrac{x}{2} \leq y \leq 2x$

と、 $x, y$ の関係をひっくり返しても同じ不等式が成立する。

このため、 $x \geq y$ で証明できれば $x \leq y$ も同様である。

以上をまとめると

$x \geq y \geq 0$ で証明できれば充分であることがわかる。

この浮動小数点環境が

$\beta$ 進 $p$ 桁の浮動小数点環境 (指数部範囲： $e_{min}, e_{max}$ ) とすると、

有限値をとる浮動小数点数 $x, y \geq 0$ はそれぞれ

$x = M_x \times \beta^{e_x - p + 1}$ $y = M_y \times \beta^{e_y - p + 1}$

と表せる。ただし　 $M_x, M_y$ は整数で $0 \leq M_x, M_y$ < $\beta^{p}$ を満たし、

$e_x, e_y$ は整数で $e_{min} \leq e_x, e_y \leq e_{max}$ である。 (*)(この事実について後で補足あり)

$M := M_x \beta^{e_x - e_y} - M_y$ とおくと

$x - y = M \times \beta^{e_y - p + 1}$

となり、 $M$ は整数なので $0 \leq M$ < $\beta^{p}$ が示されれば、

$x - y$ がこの浮動小数点環境で正確に表示できていることがわかる。 (*)(この事実について後で補足あり)

そのため、このことを示す。

仮定より $x \geq y$ なので

$x - y = M \times \beta^{e_y - p + 1} \geq 0$

であり $M \geq 0$ がわかる。

最後に

仮定より $2y \geq x$ であることから

$x - y = M \times \beta^{e_y - p + 1} \leq y \quad (= M_y \times \beta^{e_y - p + 1} )$

であるから

$M \leq M_y$ < $\beta^p$

が示され $0 \leq M$ < ${\beta}^{p}$ が証明された。

故に証明完了。

□

上の証明への補足

上の証明で唯一難しい点として、下の事実を当然として利用しました。

この事実は頭の体操的なものであるものの、

おそらくこのブログの多くの箇所で参照する事実であることから、

解説を記載しておくこととします。

Prop. (整数を用いた $\beta$ 進 $p$ 桁の浮動小数点数の表示)

浮動小数点環境が $\beta$ 進 $p$ 桁の浮動小数点環境 (指数部範囲： $e_{min}, e_{max}$ ) とすると、
有限値をとる浮動小数点数 $x \geq 0$ は $x = M \times \beta^{e - p + 1}$ と表せる。ただし　 $M$ は整数で $0 \leq M$ < $\beta^{p}$ を満たし、
$e$ は整数で $e\_{min} \leq e \leq e\_{max}$ である。
そして逆に、その $x$ が上の表示であれば、有限な浮動小数点数 $x \geq 0$ である。

Prop. の証明 – 整数を用いた $\beta$ 進 $p$ 桁の浮動小数点数の表示

$\beta$ 進 $p$ 桁の有限値をとる浮動小数点数 $x \geq 0$ は

$x = (x_0 . x_1 x_2 \dotsb x_{p-1} )_{\beta} \times \beta^{e} = \left( x_0 + \dfrac{x_1}{\beta} + \dfrac{x_2}{\beta^2} + \dotsb + \dfrac{x_{p-1}}{\beta^{p-1}} \right) \times \beta^{e}$

と表される。ただし $x_i$ は整数で $0 \leq x_i$ < $\beta$ を満たし、

$e$ は整数で $e_{min} \leq e \leq e_{max}$ である。

これは浮動小数点数の定義からである。

補足すると $x_0 \neq 0$ とできる数が特に 正規化数 と呼ばれるものであった。

この数にとらわれない、例えば

$(0 . 1 1 \dotsb 1 )_{\beta} \times \beta^{e_{min}} = \left( \dfrac{1}{\beta} + \dfrac{1}{\beta^2} + \dotsb + \dfrac{1}{\beta^{p-1}} \right) \times \beta^{e_{min}}$

という数は 非正規化数 と呼ばれる数である。この数は $x_0 \neq 0$ の形で表示することができない。これは指数部が $e_{min}$ と既に最小であるからである。