読者です 読者をやめる 読者になる 読者になる

小清水さんとコンピューター数学

コンピューター・数学 に関することを書きます

丸め誤差界の Hello World 的定理 -- Sterbenz の定理

小清水 (@curekoshimizu) です。

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

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

connpass.com

その中で、

コイン投げは確率界の 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} と既に最小であるからである。

上の  x は次のように変形できる:

 x = \left( x_0 \beta^{p-1} + x_1 \beta^{p-2} + x_2\beta^{p-3} + x_{p-1} \beta^{0} \right) \times \beta^{e-p+1}

ここで

 M := x_0 \beta^{p-1} + x_1 \beta^{p-2} + x_2\beta^{p-3} + x_{p-1} \beta^{0}

とおけばよく  M は 整数で  0 \leq M <  \beta^{p} を満たす。

逆に  M が整数で  0 \leq M <  \beta^{p} を満たすならば

 M = x_0 \beta^{p-1} + x_1 \beta^{p-2} + x_2\beta^{p-3} + x_{p-1} \beta^{0}

と表示できることから、逆も示される。

まとめ

丸め誤差界の Hello World 的定理である Sterbenz の定理 を紹介しました。

簡単な証明、簡単な条件なだけあり、

そこまで日の目を見ないかもしれませんが

そこは Hello World 、目を瞑りましょう。

浮動小数点や丸め誤差などに興味がわきましたら

math-koshimizu.hatenablog.jp

などを是非御覧ください。以上です。