🔢

魔法の数字 6755399441055744

に公開
マジックナンバー
IEEE 754
浮動小数点数
round
tech

魔法の数字

6,755,399,441,055,744.

なにこれ

浮動小数点数を整数に丸めるマジックナンバーです [1]．

使い方

  1. 適当な数値を用意します．
  2. マジックナンバーを足します．
  3. マジックナンバーを引きます．
  4. 丸められて整数部分が得られます．

なんで？

足して引いただけなのに，小数部分が吹き飛びました．実の所，これは浮動小数点数 (IEEE 754) の仕様を利用したトリックです．まずは，この数の正体と IEEE 754 の挙動から丁寧に確認して参りましょう．

正体

2^{52} + 2^{51} = 6,755,399,441,055,744 .

52 と 51 は何処から来た？というのが正直な感想でしょう．これは倍精度浮動小数点数 (double) が 53 bit の整数表現能力を有することに由来します．double は所謂二進数版の科学技術表記にして，有効数字を 53 桁確保し，残りは桁位置をずらして表すという形式をしています．ビット列にすると仮数部が 52 bit だったり正規化という表現の変換があったりして込み入ってしまうのですが，考え方自体は科学技術表記であると言って差支えありません．

仕組み

このトリックの核心は，有効数字の性質上，double が いつでも同じ細かさで実数を表せる訳ではないという点にあります．十進数でイメージすると分かり易いです．例えば有効数字が 3 桁しかない場合，1.23 は表せますが，123456.7 は 123000 みたいに丸められてしまい，小数は残りません．一般化して言えば，大きい数ほど目盛りが粗くなります．二進数とて同様です．値が大きくなるほど隣り合う表現可能な値の間隔が拡がります．この間隔のことを ULP (Unit in the Last Place) と言います．

double の有効数字は 53 桁ですから，2^{52} 以上 2^{53} 未満の範囲では ULP が丁度 1 になります．従って，この範囲の double は 1 刻みにしか並びません．要は小数部分を抱え込む余地がなくなります．この性質を逆手に取れば，小数の丸めに使うことが出来ます．つまり，2^{52} 以上 2^{53} 未満の範囲に一度押し込めば，その瞬間に小数部分が 1 の粒度に丸め落ちてくれます．これこそが 2^{52} を拠り所とする理由であります．

ひとまず整理しますと，この丸めトリックは以下のように説明できます:

  1. マジックナンバーを足すと小数部分が保持しきれなくなる．
  2. そこからマジックナンバーを引くと整数のみが戻ってくる．

2^{51} の必要性

さて，2^{52} を加えることで，確かに正の数は 2^{52} 付近に飛ばせます．しかし，このままでは負の数を扱う折に不都合が生じます．

マジックナンバーを C，目的の数を x と致しましょう．C = 2^{52} のままでは，x が負の場合に C + x < 2^{52} となり，ULP が 1 よりも小さい領域に踏み込んでしまいます．この状態では，足した瞬間に小数が消えるという保証が揺らぎ，狙った丸めになりません．そこで，C を 2^{52} のど真ん中より半ば上寄りにずらして，以下のように定め直してあげます:

C = 1.5 \times 2^{52} = 2^{52} + 2^{51} .

こうすれば，x が負の場合でも C + x がずっと [2^{52}, 2^{53}) に踏み留まります．

丸められる理由

有効数字の制約ゆえ，小数部分が切捨てられたのだと考えがちですが，実際の挙動は「銀行丸め」になります．これはトリック固有の魔法ではなく，IEEE 754 の仕様に由来するものであります．

x + C の 結果を正確に表せない時，IEEE 754 では最も近い表現可能値に丸めてから結果を保存します．その丸め規則の既定が「銀行丸め」となっています．

銀行丸めは四捨五入に似て非なるものでして，端数が 5 の場合には最寄りの偶数へ丸める規則を採ります．例えば 4.5 は四捨五入すると 5.0 になりますが，銀行丸めでは 4.0 になります．切り上げて偶数になる場合は四捨五入と同じ振舞いをします。

注意点

  • 以上の説明から解る通り，この方法は全ての x について万能ではありません．C + x が [2^{52}, 2^{53}) に入っている間だけ小数が確実に消えるという性質を利用する以上，\left|x\right| < 2^{51} の条件下で有効です．

  • 処理系によっては浮動小数点数の「丸めモード」を変更でき，ここで銀行丸め以外のモードを選択すると意図せぬ結果が得られることがあります．

  • \mathrm{NaN} や \pm\infty のような特殊値はこの手法の対象外です．

この数の起源

さて，ここまで 6,755,399,441,055,744 という数がどのように機能するかを見て参りましたが，このマジックナンバー自体は何処で生まれたのかという点にも触れておきましょう．

結論から申しますと，この手法は公式な標準規格や学術論文で提案されたものではないと見られます．IEEE 754 が定めているのは飽くまで浮動小数点数の表現形式そのものであり，或る数を足して引けば丸められるというような応用テクニックまでは扱っておりません．

この手法はプログラミング実装上の小技として自然発生的に広まったもので，低レベル処理の高速化テクニックとして昔から断片的に流通していたと推察されます．

オンラインコミュニティのみならず，OSS プロジェクトにもこの数は登場します．Windows のアプリケーションを Unix 系 OS で動かすためのツールである Wine のソースコードには，以下のコメントと伴に本記事のマジックナンバーが登場します [2]．

wine/libs/lcms2/src/lcms2_internal.h
// Fast floor conversion logic. Thanks to Sree Kotay and Stuart Nixon

この Sree Kotay さんと Stuart Nixon さんが発案者なのかどうかは不明ですが，少なくとも 1.5 \times 2^{N} を用いた高速丸めアルゴリズムを実装し，公開ソフトウェアに残した実例のひとつであることは確かです．

現代の CPU (SSE2 以降) には CVTTSD2SI 等の高速な整数変換命令があり，このトリックを使わずとも同等の処理が可能です．そう考えると，この数字は当時のハードウェアの制約を乗り越えるために生み出された遺産と言えるかもしれません．

サンプルコード

Haskell による実装例です．

main.hs
-- マジック丸め．型は Double のままだよ
round' :: Double -> Double
round' x =
  let magic = 6755399441055744 :: Double
   in magic + x - magic

main :: IO ()
main = do
  -- 切捨ての例
  print $ round' 123.456 -- 123.0

  -- 切上げの例
  print $ round' 456.789 -- 457.0
脚注

  1. ここでの浮動小数点数とは倍精度浮動小数点数 (double, f64) を指します．単精度 (float, f32) では 12582912 が使われます． ↩︎

  2. Wine Project, lcms2_internal.h, commit 9f41143, https://github.com/wine-mirror/wine/blob/d671927488486b8541cc235a73c94989a21e9caa/libs/lcms2/src/lcms2_internal.h#L156 ↩︎

Discussion