+
+

更新履歴

+
    +
  1. + : デジタルサーカス株式会社の社内記事として公開 +
    2. +
  2. + : PHP 勉強会@東京 第 180 回で発表 +
    3. +
  3. + : 公開 +
    4. +
+
+
+
+ NOTE +
+
+

+ この記事は、2025-01-23 に デジタルサーカス株式会社 の社内 Qiita Team に公開された記事をベースに、加筆修正して一般公開したものです。 +

+
+
+
+
+ NOTE +
+
+

+ この記事の内容を、PHP 勉強会@東京 第 180 回 で発表しました。 +

+
+
+
+

はじめに

+

+ 数値の範囲を指定して検索をおこなう API の中に、半開区間を指定させるものがある。半開区間とは、一方の端を含み一方の端を含まないような区間である。ここでは特に左端が閉じ右端が開いているような区間を扱う。例えば、次の区間 [3, 7) は 3 <= x < 7 であるような x の集合である。 +

+

+ ここで、この API を使って単一の値を検索することを考えたい。検索対象が整数であれば話は簡単で、1 大きい数を右端に指定してやればよい。5 を探したければ [5, 6) を渡せば目的が達成できる。 +

+

+ しかし、検索の対象が実数であればどうだろうか？ +

+
+
+

実数の半開区間

+

+ ちょうど 1 だけを含むような半開区間が作れないか考えよう。つまり、左端に 1 を、右端に 1 より少しだけ大きい値を指定して、「ちょうど 1」を表すような範囲を作れないだろうか。 +

+

+ お気付きの方もいるだろうがこれは不可能である。もしそのような区間が作れるなら、[1, p) にちょうど 1 しか含まれないような実数 p が存在する。しかし、1 と p のちょうど真ん中である (1+p) / 2 を考えると、1 よりも大きく p よりも小さいから [1, p) に含まれる。これは [1, p) が 1 しか含まないとした仮定に矛盾する。 +

+

+ 数学の世界ではこのような区間を作ることはできない。では、コンピュータ上ならばどうだろうか？ +

+
+
+

コンピュータにおける実数表現

+

+ コンピュータにおける実数の表現にはさまざまなものがあるが、ここでは最もよく使われる IEEE 754 という標準規格に従う形式、その中でも binary64 と呼ばれる形式を考えることにする。これは多くの言語で float や double と呼ばれるものと同じである。 +

+

+ binary64 は 64 bit で構成されており、無限個ある実数をすべて覆い尽くすことはできない。数学の上では存在しなかった p も、binary64 の範囲に実数を限定すれば都合のよい p を見つけることができる。 +

+
+
+

浮動小数点数で単一値を指す半開区間を作る

+

+ 結論から言うと、p は 1.0000000000000002 である。[1, 1.0000000000000002) は binary64 の範囲で 1 しか含まない。別の言い方をすれば、1 < x < 1.0000000000000002 を満たすような x は、binary64 で表せない。 +

+

+ 1 と p のビット列での表現を見てみよう。 +

+
+ 
1 = 0011111111110000000000000000000000000000000000000000000000000000
+p = 0011111111110000000000000000000000000000000000000000000000000001
+
+

+ p が 1 よりも一つ分だけ大きいのがわかるだろうか (ここでは binary64 の具体的な表現について言及していないのでそうなる保証はないのだが、あくまで雰囲気として)。 +

+

+ では、任意の値が与えられた際、それに対応する右端を得るにはどうすればよいのだろうか。IEEE 754 にはこのような用途に用いることができる nextUp という操作が定められている。 +

+

+ nextUp は、binary64 で表現できる値のうち、与えられた数よりも一つだけ大きい値を返す演算である。これを使えば、ある数 x が与えられたとき、[x, nextUp(x)) という半開区間を作ればちょうど x だけを含むような範囲を表すことができる。 +

+
+
+

PHP で nextUp を実装する

+

+ プログラミング言語によっては標準ライブラリに nextUp 相当の操作が定められているものもある。PHP には無かったので自作した。 +

+ +

+ binary64 を 64 bit の整数に変換できるなら、他の言語でもほとんど同じ方法で実装できるはずだ。 +

+
+ 
    public static function nextUp(float $x): float
+    {
+        // NaN (Not a Number) なら NaN を返す。
+        if (is_nan($x)) {
+            return NAN;
+        }
+        // 正の無限大なら正の無限大を返す。
+        if (is_infinite($x) && $x > 0) {
+            return INF;
+        }
+        // 0 なら minValue() を返す (後述)。
+        if ($x === 0.0) {
+            return self::minValue();
+        }
+        // binary64 を 64 bit 整数に変換する。
+        $u = self::floatToInt($x);
+        // 正なら整数に +1 して binary64 に戻す。
+        // 負なら整数に -1 して binary64 に戻す。
+        return $x > 0.0 ? self::intToFloat($u + 1) : self::intToFloat($u - 1);
+    }
+
+

+ 0 のときに返している minValue() は次のような値である。 +

+
+ 
    public static function minValue(): float
+    {
+        // 整数の 1 を binary64 と解釈した値を返す。
+        // binary64 で表せる最小の正の非正規化数。
+        return self::intToFloat(1);
+    }
+
+
+
+

おわりに

+

+ 頻繁に必要になるようなものではないが、いつか誰かを救えれば幸いである。 +

+
+