[インデックス 18065] ファイルの概要

このコミットは、Go言語の math/rand パッケージにおける Float32 および Float64 関数が、生成する乱数の範囲を厳密に [0, 1) に限定するための修正です。以前の実装では、特定の条件下で 1.0 を返す可能性があり、これは乱数生成の一般的な要件である [0, 1) の範囲外でした。この修正により、浮動小数点数の精度を考慮した新しい乱数生成ロジックが導入され、テストが追加されました。

コミット

commit 17dc712c18fdba4bc88fe5adf56c3ace86c765ad
Author: Jeff R. Allen <jra@nella.org>
Date:   Wed Dec 18 15:38:53 2013 -0500

    math/rand: Float32/64 must only return values in [0,1)
    
    Float32 and Float64 are now both created by taking the ratio
    of two integers which are chosen to fit entirely into the
    precision of the desired float type. The previous code
    could cast a Float64 with more than 23 bits of ".99999"
    into a Float32 of 1.0, which is not in [0,1).
    
    Float32 went from 15 to 21 ns/op (but is now correct).
    
    Fixes #6721.
    
    R=golang-dev, iant, rsc
    CC=golang-dev
    https://golang.org/cl/22730043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/17dc712c18fdba4bc88fe5adf56c3ace86c765ad

元コミット内容

math/rand: Float32/Float64 は [0,1) の値のみを返さなければならない。

Float32 と Float64 は、目的の浮動小数点型の精度に完全に収まるように選択された2つの整数の比率を取ることによって作成されるようになりました。以前のコードでは、23ビット以上の ".99999" を持つ Float64 を Float32 にキャストすると 1.0 になる可能性があり、これは [0,1) の範囲外でした。

Float32 は 15 ns/op から 21 ns/op になりました（しかし、現在は正しいです）。

Fixes #6721.

変更の背景

この変更の背景には、math/rand パッケージの Float32() および Float64() 関数が、乱数生成の標準的な慣習である [0, 1) の範囲（0を含み、1を含まない）を厳密に遵守していなかったという問題があります。

具体的には、以前の実装では Float64() が r.Int63() / (1 << 63) という計算を行っていました。Int63() は int64 型の非負の擬似乱数を返しますが、その最大値は (1 << 63) - 1 です。この値を (1 << 63) で割ると、理論的には 1.0 には到達しません。しかし、Float64() の結果を Float32() にキャストする際に、浮動小数点数の精度問題が発生しました。

Float64 は倍精度浮動小数点数であり、約15-17桁の精度を持ちます。一方、Float32 は単精度浮動小数点数であり、約6-9桁の精度しか持ちません。Float64 で生成された 0.9999999999999999 のような値（1に非常に近いが1ではない値）が Float32 に変換される際、Float32 の表現可能な範囲で最も近い値が 1.0 となってしまうことがありました。これは、Float32 の仮数部が23ビットしかないため、Float64 の持つより高い精度を正確に表現しきれないことに起因します。

乱数生成において [0, 1) の範囲は非常に重要です。例えば、確率計算やシミュレーションにおいて、1.0 が含まれてしまうと、期待される結果にずれが生じる可能性があります。この問題は Go の Issue #6721 として報告され、このコミットはその修正を目的としています。

前提知識の解説

浮動小数点数表現 (IEEE 754)

Float32 (単精度浮動小数点数): IEEE 754 規格で定義されており、32ビットを使用します。
- 1ビットの符号部
- 8ビットの指数部
- 23ビットの仮数部（ただし、暗黙の1ビットがあるため実質24ビットの精度）
- これにより、約7桁の十進精度を持ちます。表現できる最大値は約 3.4 x 10^38、最小の正の正規化数は約 1.2 x 10^-38 です。
Float64 (倍精度浮動小数点数): IEEE 754 規格で定義されており、64ビットを使用します。
- 1ビットの符号部
- 11ビットの指数部
- 52ビットの仮数部（ただし、暗黙の1ビットがあるため実質53ビットの精度）
- これにより、約15-17桁の十進精度を持ちます。表現できる最大値は約 1.8 x 10^308、最小の正の正規化数は約 2.2 x 10^-308 です。

浮動小数点数は、有限のビット数で実数を近似するため、常に精度誤差が伴います。特に、ある精度で表現された数を低い精度に変換（キャスト）する際には、元の値が正確に表現できない場合、最も近い表現可能な値に丸められます。この丸め処理が、0.999... のような値を 1.0 にしてしまう原因となります。

擬似乱数生成 (PRNG)

擬似乱数生成器は、初期シード値に基づいて、統計的にランダムに見える数値のシーケンスを生成するアルゴリズムです。真の乱数とは異なり、同じシード値からは常に同じシーケンスが生成されます。

[0, 1) の範囲: 多くの乱数生成器は、0を含み1を含まない半開区間 [0, 1) の浮動小数点数を生成するように設計されています。これは、確率論や統計学において、イベントの確率が0から1の間にあり、100%の確率（1.0）は通常、特定のイベントが確実に発生することを示すため、乱数としては通常含まれないという慣習に基づいています。

ビットシフト演算

1 << N: 整数 1 を左に N ビットシフトする操作です。これは 2^N と同じ意味になります。例えば、1 << 63 は 2^63 を表します。

技術的詳細

このコミットの技術的な核心は、Float32 と Float64 の乱数生成において、浮動小数点数の精度限界を考慮し、1.0 が生成される可能性を排除することです。

以前の実装の問題点

Float64(): float64(r.Int63()) / (1 << 63)
- r.Int63() は [0, 2^63 - 1] の範囲の int64 を生成します。
- これを 2^63 で割ることで、[0, (2^63 - 1) / 2^63] の範囲の float64 が得られます。この最大値は 1.0 に非常に近いですが、1.0 ではありません。
Float32(): float32(r.Float64())
- Float64() で生成された float64 値を float32 にキャストしていました。
- 前述の通り、float64 で 0.9999999999999999 のような値が生成された場合、float32 の精度ではこれを正確に表現できず、最も近い値である 1.0 に丸められてしまうことがありました。これが Fixes #6721 の直接の原因です。

新しい実装の戦略

新しい実装では、この丸め誤差による 1.0 の生成を防ぐために、浮動小数点数の仮数部のビット数に合わせて、より少ないビット数の整数を生成し、それを適切なスケールで割る方法を採用しています。

Float64(): float64(r.Int63n(1<<53)) / (1 << 53)
- Float64 の仮数部は52ビット（暗黙の1ビットを含めると53ビット）です。
- r.Int63n(1<<53) は、[0, (1<<53) - 1] の範囲の int64 を生成します。つまり、2^53 未満の非負整数です。
- この値を (1 << 53) で割ることで、[0, ((1<<53) - 1) / (1<<53)) の範囲の float64 が得られます。
- この方法では、生成される整数が Float64 の仮数部で正確に表現できる範囲に収まるため、1.0 に丸められる可能性がなくなります。1.0 に最も近い値は 1 - 2^-53 となります。
Float32(): float32(r.Int31n(1<<24)) / (1 << 24)
- Float32 の仮数部は23ビット（暗黙の1ビットを含めると24ビット）です。
- r.Int31n(1<<24) は、[0, (1<<24) - 1] の範囲の int32 を生成します。つまり、2^24 未満の非負整数です。
- この値を (1 << 24) で割ることで、[0, ((1<<24) - 1) / (1<<24)) の範囲の float32 が得られます。
- 同様に、生成される整数が Float32 の仮数部で正確に表現できる範囲に収まるため、1.0 に丸められる可能性がなくなります。1.0 に最も近い値は 1 - 2^-24 となります。

この変更により、Float32() のパフォーマンスが 15 ns/op から 21 ns/op に悪化していますが、これは正確性を確保するためのトレードオフとして許容されています。

テストの追加

問題が7533753回の呼び出し後に発生したという報告に基づき、TestFloat32 という新しいテストが追加されました。このテストは Float32() を1000万回呼び出し、各結果が 1 以上でないことを確認します。これにより、以前のバグが再発しないことを保証します。

コアとなるコードの変更箇所

diff --git a/src/pkg/math/rand/example_test.go b/src/pkg/math/rand/example_test.go
index f429914531..b93a371a04 100644
--- a/src/pkg/math/rand/example_test.go
+++ b/src/pkg/math/rand/example_test.go
@@ -83,8 +83,8 @@ func Example_rand() {
 	// Perm generates a random permutation of the numbers [0, n).
 	show("Perm", r.Perm(5), r.Perm(5), r.Perm(5))
 	// Output:
-	// Float32     0.2635776           0.6358173           0.6718283
-	// Float64     0.628605430454327   0.4504798828572669  0.9562755949377957
+	// Float32     0.73793465          0.38461488          0.9940225
+	// Float64     0.6919607852308565  0.29140004584133117 0.2262092163027547
 	// ExpFloat64  0.3362240648200941  1.4256072328483647  0.24354758816173044
 	// NormFloat64 0.17233959114940064 1.577014951434847   0.04259129641113857
 	// Int31       1501292890          1486668269          182840835
diff --git a/src/pkg/math/rand/rand.go b/src/pkg/math/rand/rand.go
index 04fb67d19d..d3ea840178 100644
--- a/src/pkg/math/rand/rand.go
+++ b/src/pkg/math/rand/rand.go
@@ -95,10 +95,10 @@ func (r *Rand) Intn(n int) int {
 }\n \n // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).\n-func (r *Rand) Float64() float64 { return float64(r.Int63()) / (1 << 63) }\n+func (r *Rand) Float64() float64 { return float64(r.Int63n(1<<53)) / (1 << 53) }\n \n // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0).\n-func (r *Rand) Float32() float32 { return float32(r.Float64()) }\n+func (r *Rand) Float32() float32 { return float32(r.Int31n(1<<24)) / (1 << 24) }\n \n // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).\n func (r *Rand) Perm(n int) []int {\ndiff --git a/src/pkg/math/rand/rand_test.go b/src/pkg/math/rand/rand_test.go
index 4f0a8d0ee9..c174c613f4 100644
--- a/src/pkg/math/rand/rand_test.go
+++ b/src/pkg/math/rand/rand_test.go
@@ -322,6 +322,17 @@ func TestExpTables(t *testing.T) {\n \t}\n }\n \n+// For issue 6721, the problem came after 7533753 calls, so check 10e6.\n+func TestFloat32(t *testing.T) {\n+\tr := New(NewSource(1))\n+\tfor ct := 0; ct < 10e6; ct++ {\n+\t\tf := r.Float32()\n+\t\tif f >= 1 {\n+\t\t\tt.Fatal(\"Float32() should be in range [0,1). ct:\", ct, \"f:\", f)\n+\t\t}\n+\t}\n+}\n+\n // Benchmarks\n \n func BenchmarkInt63Threadsafe(b *testing.B) {\
@@ -358,6 +369,13 @@ func BenchmarkInt31n1000(b *testing.B) {\n \t}\n }\n \n+func BenchmarkFloat32(b *testing.B) {\n+\tr := New(NewSource(1))\n+\tfor n := b.N; n > 0; n-- {\n+\t\tr.Float32()\n+\t}\n+}\n+\n func BenchmarkPerm3(b *testing.B) {\n \tr := New(NewSource(1))\n \tfor n := b.N; n > 0; n-- {\

コアとなるコードの解説

`src/pkg/math/rand/rand.go` の変更

Float64() 関数の変更:
- 変更前: func (r *Rand) Float64() float64 { return float64(r.Int63()) / (1 << 63) }
- 変更後: func (r *Rand) Float64() float64 { return float64(r.Int63n(1<<53)) / (1 << 53) }
- 以前は Int63() で生成された63ビットの乱数を 2^63 で割っていましたが、新しい実装では Int63n(1<<53) を使用して 2^53 未満の乱数を生成し、それを 2^53 で割っています。これにより、Float64 の仮数部（53ビット）で正確に表現できる範囲の乱数を生成し、1.0 に丸められる可能性を排除しています。
Float32() 関数の変更:
- 変更前: func (r *Rand) Float32() float32 { return float32(r.Float64()) }
- 変更後: func (r *Rand) Float32() float32 { return float32(r.Int31n(1<<24)) / (1 << 24) }
- 以前は Float64() の結果を Float32 にキャストしていましたが、この方法では精度問題が発生していました。新しい実装では、Int31n(1<<24) を使用して 2^24 未満の乱数を生成し、それを 2^24 で割ることで、Float32 の仮数部（24ビット）で正確に表現できる範囲の乱数を直接生成しています。これにより、1.0 に丸められる可能性がなくなります。

`src/pkg/math/rand/rand_test.go` の変更

TestFloat32 関数の追加:
- この新しいテスト関数は、Float32() が [0, 1) の範囲を厳密に守っていることを検証します。
- r := New(NewSource(1)) で固定シードの乱数生成器を初期化します。
- for ct := 0; ct < 10e6; ct++ ループで、Float32() を1000万回呼び出します。
- if f >= 1 の条件で、生成された乱数 f が 1 以上である場合に t.Fatal を呼び出してテストを失敗させます。これは、[0, 1) の範囲外の値が生成されたことを意味します。
- このテストは、Issue #6721 で報告された問題が、多数の呼び出し後に発生したという背景に基づいて設計されています。
BenchmarkFloat32 関数の追加:
- Float32() 関数のパフォーマンスを測定するためのベンチマークテストが追加されました。コミットメッセージにあるように、この変更により Float32() のパフォーマンスは若干低下していますが、これは正確性を確保するための許容範囲内のトレードオフとされています。

`src/pkg/math/rand/example_test.go` の変更

Example_rand() 関数の出力例が、新しい乱数生成ロジックによって生成される値に合わせて更新されています。これは機能的な変更ではなく、テストの出力が実際の動作と一致するようにするための調整です。

これらの変更により、math/rand パッケージの Float32 および Float64 関数は、より堅牢で正確な [0, 1) 範囲の乱数生成を提供するようになりました。

参考にした情報源リンク

コミット情報: /home/orange/Project/comemo/commit_data/18065.txt
IEEE 754 浮動小数点数標準に関する一般的な知識
擬似乱数生成に関する一般的な知識
Go言語の math/rand パッケージのドキュメント (Go公式ドキュメント)
Go Issue #6721 の内容 (GitHub)

Keyboard shortcuts

comemo