blob: 961cb89d1691d934af72053d92a0ff4cf32abb15 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
---
[article]
uuid = "39d3d137-f18d-4d88-8ef6-7be9cc2f3f0b"
title = "浮動小数点数の半開区間で単一値を表現する"
description = "IEEE 754 の nextUp 操作を用いて、浮動小数点数の半開区間で単一値を表現するテクニックを紹介する。"
tags = [
"float",
"php",
]
[[article.revisions]]
date = "2025-01-23"
remark = "デジタルサーカス株式会社の社内記事として公開"
isInternal = true
[[article.revisions]]
date = "2025-10-29"
remark = "PHP 勉強会@東京 第 180 回で発表"
isInternal = true
[[article.revisions]]
date = "2025-10-31"
remark = "公開"
---
::: note
この記事は、2025-01-23 に [デジタルサーカス株式会社](https://www.dgcircus.com/) の社内 Qiita Team に公開された記事をベースに、加筆修正して一般公開したものです。
:::
::: note
この記事の内容を、[PHP 勉強会@東京 第 180 回](/slides/2025-10-29/phpstudy-tokyo-180/) で発表しました。
:::
{#intro}
# はじめに
数値の範囲を指定して検索をおこなう API の中に、半開区間を指定させるものがある。半開区間とは、一方の端を含み一方の端を含まないような区間である。ここでは特に左端が閉じ右端が開いているような区間を扱う。例えば、次の区間 `[3, 7)` は `3 <= x < 7` であるような `x` の集合である。
ここで、この API を使って単一の値を検索することを考えたい。検索対象が整数であれば話は簡単で、1 大きい数を右端に指定してやればよい。5 を探したければ `[5, 6)` を渡せば目的が達成できる。
しかし、検索の対象が実数であればどうだろうか？
{#half-open-real-interval}
# 実数の半開区間
ちょうど `1` だけを含むような半開区間が作れないか考えよう。つまり、左端に `1` を、右端に `1` より少しだけ大きい値を指定して、「ちょうど `1`」を表すような範囲を作れないだろうか。
お気付きの方もいるだろうがこれは不可能である。もしそのような区間が作れるなら、`[1, p)` にちょうど `1` しか含まれないような実数 `p` が存在する。しかし、`1` と `p` のちょうど真ん中である `(1+p) / 2` を考えると、`1` よりも大きく `p` よりも小さいから `[1, p)` に含まれる。これは `[1, p)` が `1` しか含まないとした仮定に矛盾する。
数学の世界ではこのような区間を作ることはできない。では、コンピュータ上ならばどうだろうか？
{#float-numbers}
# コンピュータにおける実数表現
コンピュータにおける実数の表現にはさまざまなものがあるが、ここでは最もよく使われる IEEE 754 という標準規格に従う形式、その中でも `binary64` と呼ばれる形式を考えることにする。これは多くの言語で `float` や `double` と呼ばれるものと同じである。
`binary64` は 64 bit で構成されており、無限個ある実数をすべて覆い尽くすことはできない。数学の上では存在しなかった `p` も、`binary64` の範囲に実数を限定すれば都合のよい `p` を見つけることができる。
{#single-value-float-interval}
# 浮動小数点数で単一値を指す半開区間を作る
結論から言うと、`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` だけを含むような範囲を表すことができる。
{#nextup-in-php}
# PHP で nextUp を実装する
プログラミング言語によっては標準ライブラリに `nextUp` 相当の操作が定められているものもある。
PHP には無かったので自作した。
* GitHub: https://github.com/nsfisis/php-next-after
* Packagist: https://packagist.org/packages/nsfisis/next-after
`binary64` を 64 bit の整数に変換できるなら、他の言語でもほとんど同じ方法で実装できるはずだ。
```php
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()` は次のような値である。
```php
public static function minValue(): float
{
// 整数の 1 を binary64 と解釈した値を返す。
// binary64 で表せる最小の正の非正規化数。
return self::intToFloat(1);
}
```
{#outro}
# おわりに
頻繁に必要になるようなものではないが、いつか誰かを救えれば幸いである。
|
