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

このコミットは、Go言語の math/big パッケージ内の Rat 型に、IEEE 754 倍精度浮動小数点数（float64）との相互変換を行う SetFloat64 および Float64 メソッドを追加するものです。これにより、任意精度有理数と標準の浮動小数点数との間の変換が、より正確かつ効率的に行えるようになります。

コミット

commit 961195ae6995a72c6f329e6397d93d62ed09135e
Author: Alan Donovan <adonovan@google.com>
Date:   Mon Jan 28 18:00:15 2013 -0500

    math/big: add Rat.{,Set}Float64 methods for IEEE 754 conversions.
    
    Added tests, using input data from strconv.ParseFloat.
    Thanks to rsc for most of the test code.
    
    math/big could use some good package-level documentation.
    
    R=remyoudompheng, rsc
    CC=golang-dev
    https://golang.org/cl/6930059

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

https://github.com/golang/go/commit/961195ae6995a72c6f329e6397d93d62ed09135e

元コミット内容

math/big パッケージの Rat 型に、IEEE 754 浮動小数点数との変換のための Rat.Float64 および Rat.SetFloat64 メソッドを追加しました。strconv.ParseFloat からの入力データを使用してテストも追加しました。テストコードの大部分は rsc に感謝します。math/big パッケージには、より良いパッケージレベルのドキュメントが必要です。

変更の背景

Go言語の math/big パッケージは、任意精度の数値演算を提供し、標準の int や float64 型では表現できない非常に大きな数値や、高い精度が要求される計算に対応します。特に Rat 型は有理数を分子と分母で表現するため、浮動小数点数で発生する丸め誤差を完全に回避できます。

しかし、現実世界のデータや他のシステムとの連携では、標準の float64 型（IEEE 754 倍精度浮動小数点数）が広く用いられています。これまでの math/big.Rat には、float64 から Rat へ、または Rat から float64 へと、正確かつ効率的に変換する直接的なメソッドがありませんでした。この欠如は、math/big.Rat を使用して計算された結果を float64 として出力したり、float64 の入力値を Rat として正確に処理したりする際に、開発者が手動で複雑な変換ロジックを実装する必要があることを意味していました。

このコミットは、このギャップを埋めることを目的としています。SetFloat64 メソッドは float64 の値をその正確な有理数表現に変換し、Float64 メソッドは Rat の値を最も近い float64 表現に変換します。これにより、math/big パッケージの利便性と実用性が向上し、任意精度計算と標準浮動小数点計算との間のシームレスな連携が可能になります。特に、float64 のバイナリ表現を正確に解析し、有理数に変換するロジックは、浮動小数点数の特性を深く理解している必要があります。

前提知識の解説

1. IEEE 754 浮動小数点数（float64）

Go言語の float64 は、IEEE 754 規格に準拠した倍精度浮動小数点数です。これは64ビットで構成され、以下の要素からなります。

• 符号部 (1ビット): 数値が正か負かを示します（0: 正、1: 負）。
• 指数部 (11ビット): 数値のスケール（桁）を表します。バイアス付き表現（通常1023のバイアス）が用いられ、実際の指数は格納された値からバイアスを引いたものです。これにより、負の指数も表現できます。正規化された数値の場合、指数部の範囲は -1022 から +1023 です。
• 仮数部 (52ビット): 数値の精度（有効数字）を表します。正規化された数値の場合、仮数部の最上位ビットは常に1であるため、明示的に格納されず、暗黙の1ビットとして扱われます（これにより53ビットの精度が得られます）。

float64 は、約15〜17桁の10進数精度を持ち、約 ±10^-308 から ±10³⁰⁸ の範囲の数値を表現できます。しかし、すべての実数を正確に表現できるわけではなく、特に10進数の小数（例: 0.1）は2進数では無限小数になるため、float64 で表現すると丸め誤差が生じます。非有限値（NaN: Not a Number, Inf: Infinity）も表現可能です。

2. math/big パッケージと Rat 型

Goの math/big パッケージは、標準の組み込み型では扱えないような、任意精度の数値演算を提供します。これにより、非常に大きな整数、高精度な浮動小数点数、そして有理数を扱うことができます。

• Int: 任意精度の符号付き整数を扱います。
• Float: 任意精度の浮動小数点数を扱います。
• Rat: 任意精度の有理数を扱います。有理数は a/b の形式で表現され、分子 a と分母 b はそれぞれ *big.Int 型で保持されます。これにより、浮動小数点数で発生する丸め誤差を完全に回避し、正確な分数計算が可能です。

math/big パッケージのメソッドは、通常、レシーバをポインタで受け取り、そのレシーバ自身を返すことで、メソッドチェーンを可能にし、メモリの再利用を促進します。

3. 浮動小数点数の変換と丸め

浮動小数点数の変換において、特に重要なのは「丸め」の概念です。IEEE 754 規格では、いくつかの丸めモードが定義されていますが、最も一般的なのは「最近接偶数への丸め（round half to even）」です。これは、ちょうど中間点にある値（例: 0.5）を丸める際に、結果が偶数になるように丸めるというルールです。これにより、統計的なバイアスが減少します。

float64 から Rat への変換は、float64 のバイナリ表現（符号、指数、仮数）を正確に解析し、それを分数形式に再構築することで行われます。この変換は、有限な float64 であれば常に正確な有理数表現が得られます。

一方、Rat から float64 への変換は、有理数が float64 で正確に表現できない場合に丸めが必要になります。この際、最も近い float64 値を選択し、必要に応じて「最近接偶数への丸め」ルールが適用されます。

技術的詳細

このコミットで追加された主要なメソッドは Rat.SetFloat64 と Rat.Float64 です。

Rat.SetFloat64(f float64) *Rat

このメソッドは、与えられた float64 値 f を、Rat 型のレシーバ z に正確な有理数として設定します。f が非有限値（NaNまたはInf）の場合、nil を返します。

内部的には、math.Float64bits(f) を使用して float64 のビット表現を取得し、符号、指数、仮数に分解します。

1. ビットの分解:

   • bits := math.Float64bits(f): float64 の64ビット表現を uint64 として取得。
   • mantissa := bits & (1<<52 - 1): 仮数部（下位52ビット）を抽出。
   • exp := int((bits >> 52) & expMask): 指数部（52ビット目から11ビット）を抽出。expMask は 1<<11 - 1 で、11ビット全てが1のマスク。

2. 特殊な指数値の処理:

   • expMask と等しい場合（全て1）は、非有限値（NaNまたはInf）なので nil を返す。
   • 0 の場合（全て0）は、非正規化数（denormal）であり、指数は -1022 として扱われる。
   • それ以外（正規化数）の場合、仮数部に暗黙の先頭ビット 1<<52 を追加し、指数からバイアス 1023 を引く。

3. シフト量の計算:

   • shift := 52 - exp: 仮数部を正規化するために必要なシフト量を計算。これは、仮数部を 1.xxxx の形式から整数に変換し、さらに 2^exp を考慮したものです。

4. 最適化:

   • for mantissa&1 == 0 && shift > 0: 仮数部の最下位ビットが0であり、かつシフト量が正の場合、仮数部を右シフトし、シフト量を減らす。これにより、共通因子を事前に除去し、正規化を部分的に行うことで、後の計算を簡略化します。

5. 分子と分母の設定:

   • z.a.SetUint64(mantissa): Rat の分子 z.a に計算された仮数部を設定。
   • z.a.neg = f < 0: float64 の符号を分子に適用。
   • z.b.Set(intOne): Rat の分母 z.b を1に初期化。
   • if shift > 0: シフト量が正の場合、分母を左シフト（z.b.Lsh(&z.b, uint(shift))）。これは、mantissa / 2^shift を表現するため。
   • else: シフト量が負の場合、分子を左シフト（z.a.Lsh(&z.a, uint(-shift))）。これは、mantissa * 2^(-shift) を表現するため。

6. 正規化:

   • return z.norm(): 最終的に Rat を正規化（分子と分母の最大公約数で割るなど）して返す。

Rat.Float64() (f float64, exact bool)

このメソッドは、Rat 型のレシーバ z を最も近い float64 値に変換し、その変換が正確であったかどうかを示す exact ブール値を返します。

内部的には、quotToFloat というヘルパー関数を呼び出して、非負の float64 値と正確性フラグを取得します。

1. 分母の処理:

   • b := z.b.abs: Rat の分母の絶対値を取得。
   • if len(b) == 0: 分母が0の場合（Rat が無限大を表す場合）、分母を1に設定（これは quotToFloat の前条件を満たすため）。

2. quotToFloat の呼び出し:

   • f, exact = quotToFloat(z.a.abs, b): 分子の絶対値と分母を quotToFloat に渡し、結果の float64 と exact フラグを取得。

3. 符号の適用:

   • if z.a.neg: Rat の分子が負の場合、結果の float64 に負の符号を適用。

4. 結果の返却:

   • return f, exact: 変換された float64 値と正確性フラグを返す。

quotToFloat(a, b nat) (f float64, exact bool) ヘルパー関数

この関数は、非負の nat 型（math/big 内部の符号なし整数スライス）である a と b を受け取り、a/b の商に最も近い IEEE 754 倍精度浮動小数点数を返します。丸めは「最近接偶数への丸め」を使用します。

1. 初期チェック:

   • if alen == 0: a が0の場合、0, true を返す。
   • if blen == 0: b が0の場合、パニック（ゼロ除算）。

2. 正規化のためのシフト:

   • exp := alen - blen: 指数を概算。
   • shift := 54 - exp: a/b の商が [1<<53, 1<<55) の範囲に入るように a または b をシフトする量を計算。これは float64 の仮数部（52ビット）に加えて、丸めのために必要な追加のビット（2〜3ビット）を確保するためです。
   • a2 = a2.shl(a2, uint(shift)) または b2 = b2.shl(b2, uint(-shift)): 実際にシフトを実行。

3. 商と剰余の計算:

   • q, r := q.div(a2, a2, b2): シフトされた a2 を b2 で除算し、商 q と剰余 r を計算。
   • mantissa := low64(q): 商 q の下位64ビットを仮数として取得。
   • haveRem := len(r) > 0: 剰余があるかどうかをチェック。

4. 仮数部の調整:

   • if mantissa>>54 == 1: 商が54ビットに収まらなかった場合（つまり、シフトが大きすぎた場合）、仮数部を右シフトし、指数をインクリメントして調整。

5. 丸め:

   • exact = !haveRem: 剰余がなければ正確。
   • if mantissa&1 != 0: 仮数部の最下位ビットが1の場合（つまり、丸めが必要な場合）。
     • if haveRem || mantissa&2 != 0: 剰余があるか、または仮数部の下から2番目のビットが1の場合（最近接偶数への丸めルール）。
     • mantissa++: 仮数部をインクリメント。
     • if mantissa >= 1<<54: 仮数部がオーバーフローした場合、右シフトして指数をインクリメント。
   • mantissa >>= 1: 丸めビットを破棄。これで仮数部は 2^53 スケールになる。

6. 最終的な float64 の構築:

   • f = math.Ldexp(float64(mantissa), exp-53): 仮数部と調整された指数から float64 を構築。exp-53 は、仮数部が 2^53 スケールであることを考慮したものです。
   • if math.IsInf(f, 0): 結果が無限大の場合、exact は false に設定。

テスト (rat_test.go)

rat_test.go には、Rat.SetFloat64 と Rat.Float64 の正確性を検証するための広範なテストが追加されています。

• float64inputs: strconv.ParseFloat のテストデータから借用した、様々な種類の float64 値（正規化数、非正規化数、非常に大きい/小さい数、境界値など）を含む文字列スライス。
• TestFloat64SpecialCases: float64inputs の各値について、以下の検証を行います。
  1. Rat.SetString で Rat に変換し、その Rat を Float64 で float64 に変換した結果が、strconv.ParseFloat の結果と一致するかどうか。
  2. 変換された float64 が、元の Rat の最も近い近似値であるかどうかを checkIsBestApprox で検証。
  3. float64 -> Rat -> float64 のラウンドトリップが非損失的であるかどうかを checkNonLossyRoundtrip で検証。
  4. Rat.Float64() が返す exact フラグが正しいかどうかを検証。
• TestFloat64Distribution: 広範囲の（符号、仮数、指数）の組み合わせを生成し、Rat.Float64() が常に最も近い float64 近似値を選択するかどうかを検証します。
• TestSetFloat64NonFinite: math.NaN(), math.Inf(+1), math.Inf(-1) などの非有限値を SetFloat64 に渡した場合に nil が返されることを確認します。
• checkNonLossyRoundtrip: float64 から Rat への変換、そしてその Rat から float64 への再変換が、元の float64 と完全に一致するかどうかを検証します。
• checkIsBestApprox: ある Rat 値 r を float64 に変換した結果 f が、f の前後にある float64 値 f0, f1 よりも r に近いかどうかを検証します。これにより、丸めが正しく行われていることを確認します。特に、ちょうど中間点にある場合は「最近接偶数への丸め」が適用されているかを isEven ヘルパー関数を使ってチェックします。
• TestIsFinite: isFinite ヘルパー関数が float64 の有限性を正しく判定するかどうかを検証します。

これらのテストは、Rat と float64 の間の変換が、IEEE 754 規格に厳密に準拠し、高い精度と正確性を持って行われることを保証するために非常に重要です。

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

src/pkg/math/big/rat.go

• import "math" の追加。
• Rat 型に以下のメソッドが追加されました。
  • SetFloat64(f float64) *Rat: float64 を Rat に変換。
  • Float64() (f float64, exact bool): Rat を float64 に変換。
• 以下のヘルパー関数が追加されました。
  • isFinite(f float64) bool: float64 が有限値であるかを判定。
  • low64(z nat) uint64: nat 型の下位64ビットを取得。
  • quotToFloat(a, b nat) (f float64, exact bool): a/b の商を float64 に変換（丸め処理を含む）。

src/pkg/math/big/rat_test.go

• import "math", "strconv", "strings" の追加。
• float64inputs という、strconv.ParseFloat のテストデータから借用した float64 の文字列表現の配列が追加されました。
• 以下のテスト関数が追加されました。
  • TestFloat64SpecialCases(t *testing.T)
  • TestFloat64Distribution(t *testing.T)
  • TestSetFloat64NonFinite(t *testing.T)
  • checkNonLossyRoundtrip(t *testing.T, f float64)
  • delta(r *Rat, f float64) *Rat
  • checkIsBestApprox(t *testing.T, f float64, r *Rat) bool
  • isEven(f float64) bool
  • TestIsFinite(t *testing.T)

コアとなるコードの解説

Rat.SetFloat64 メソッド

このメソッドは、float64 のバイナリ表現を解析し、それを正確な有理数に変換する中心的なロジックを含んでいます。

func (z *Rat) SetFloat64(f float64) *Rat {
	const expMask = 1<<11 - 1 // 指数部11ビットのマスク
	bits := math.Float64bits(f) // float64のビット表現を取得
	mantissa := bits & (1<<52 - 1) // 仮数部（下位52ビット）を抽出
	exp := int((bits >> 52) & expMask) // 指数部を抽出

	switch exp {
	case expMask: // 非有限値 (NaN, Inf)
		return nil
	case 0: // 非正規化数 (denormal)
		exp -= 1022 // 非正規化数の指数は-1022
	default: // 正規化数 (normal)
		mantissa |= 1 << 52 // 暗黙の先頭ビット（1）を追加
		exp -= 1023 // バイアス（1023）を引く
	}

	shift := 52 - exp // 仮数部を整数に変換するためのシフト量

	// 最適化: 仮数部の末尾の0を削除し、シフト量を調整
	for mantissa&1 == 0 && shift > 0 {
		mantissa >>= 1
		shift--
	}

	z.a.SetUint64(mantissa) // 仮数部を分子に設定
	z.a.neg = f < 0 // float64の符号を分子に適用
	z.b.Set(intOne) // 分母を1に設定

	if shift > 0 {
		z.b.Lsh(&z.b, uint(shift)) // 分母を左シフト (2^shift を掛ける)
	} else {
		z.a.Lsh(&z.a, uint(-shift)) // 分子を左シフト (2^(-shift) を掛ける)
	}
	return z.norm() // 正規化して返す
}

このコードは、IEEE 754 浮動小数点数の構造を直接操作し、float64 が mantissa * 2^exp の形式で表現されることを利用して、それを mantissa / 2^(-exp) または mantissa * 2^exp の有理数形式に変換しています。特に、非正規化数と正規化数の処理、そして暗黙の先頭ビットの扱いが重要です。

quotToFloat ヘルパー関数

この関数は、Rat から float64 への変換において、丸め処理を含む核心部分を担っています。

func quotToFloat(a, b nat) (f float64, exact bool) {
	// ... (省略: 初期チェック、シフト処理) ...

	var q nat
	q, r := q.div(a2, a2, b2) // 商と剰余を計算
	mantissa := low64(q) // 商の下位64ビットを仮数として取得
	haveRem := len(r) > 0 // 剰余があるか

	// ... (省略: 仮数部の調整) ...

	// 丸め処理
	exact = !haveRem // 剰余がなければ正確
	if mantissa&1 != 0 { // 仮数部の最下位ビットが1の場合（丸めが必要）
		exact = false
		if haveRem || mantissa&2 != 0 { // 剰余があるか、または下から2番目のビットが1の場合（最近接偶数への丸め）
			if mantissa++; mantissa >= 1<<54 { // 仮数部をインクリメントし、オーバーフローをチェック
				mantissa >>= 1 // オーバーフローした場合、右シフトして指数を調整
				exp++
			}
		}
	}
	mantissa >>= 1 // 丸めビットを破棄。仮数部は2^53スケールになる

	f = math.Ldexp(float64(mantissa), exp-53) // 仮数部と指数からfloat64を構築
	if math.IsInf(f, 0) {
		exact = false
	}
	return
}

この関数は、a/b の商を計算し、その結果を float64 の仮数部と指数部にマッピングします。特に注目すべきは、IEEE 754 の「最近接偶数への丸め」ルールを実装している点です。これは、ちょうど中間点にある値（例: 0.5）を丸める際に、結果が偶数になるように調整することで、丸め誤差の統計的な偏りを防ぎます。mantissa&1 と mantissa&2 のチェックは、この丸めルールを適用するためのものです。

関連リンク

• Go言語 math/big パッケージ公式ドキュメント: https://pkg.go.dev/math/big
• IEEE 754 浮動小数点数標準 (Wikipedia): https://ja.wikipedia.org/wiki/IEEE_754
• Go言語 strconv パッケージ公式ドキュメント: https://pkg.go.dev/strconv

参考にした情報源リンク

• Go言語 math/big パッケージの Rat 型と float64 変換に関する解説記事: https://ubc.ca
• Go言語 math/big パッケージの概要: https://manning.com
• IEEE 754 倍精度浮動小数点数形式に関する詳細: https://gitconnected.com
• strconv.ParseFloat のテストデータに関する情報: https://go.dev
• math/big パッケージの設計と使用パターン: https://faun.pub