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

このコミットは、Go言語の標準ライブラリであるmath/bigパッケージ内のint.goファイルに対するものです。math/bigパッケージは、Go言語が標準で提供する整数型（int, int32, int64など）では表現できない、任意精度の整数演算を可能にするための機能を提供します。これにより、非常に大きな数や、桁数が事前に分からないような計算を正確に行うことができます。

int.goファイルは、このパッケージの中核をなし、任意精度整数の表現（Int型）や、加算、減算、乗算、除算、最大公約数（GCD）の計算など、様々な算術演算の実装を含んでいます。

コミット

commit f4240666be0a267b4e5c793b795e9af11b080e9f
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Jun 13 10:29:06 2012 -0700

    math/big: fix binaryGCD
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/6297085

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

https://github.com/golang/go/commit/f4240666be0a267b4e5c793b795e9af11b080e9f

元コミット内容

math/big: fix binaryGCD

R=rsc
CC=golang-dev
https://golang.org/cl/6297085

変更の背景

このコミットは、math/bigパッケージ内のbinaryGCD関数における潜在的なバグを修正することを目的としています。binaryGCD関数は、2つの任意精度整数の最大公約数（GCD）を計算するために使用されます。この関数は、ドナルド・クヌースの著書「The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B」に記述されているバイナリGCDアルゴリズム（またはスタインのアルゴリズム）の実装です。

バイナリGCDアルゴリズムは、通常、入力が正の整数であることを前提としています。元の実装では、関数冒頭でユークリッドの互除法に似た初期処理を行い、2つの入力値aとbをuとvに設定し、それらのサイズを近似的に揃える試みをしていました。しかし、この初期処理の結果、vがゼロになる可能性があり、その後のバイナリGCDアルゴリズムの主要なループがゼロ除算や無限ループなどの不正な動作を引き起こす可能性がありました。

この修正は、vがゼロになった場合に、バイナリGCDアルゴリズムの残りの部分を実行する前に、その特殊なケースを適切に処理することで、関数の堅牢性と正確性を保証します。gcd(X, 0) = Xという数学的な性質に基づき、vがゼロになった場合はuがそのままGCDとなるため、uを返すように変更されました。

前提知識の解説

Go言語の`math/big`パッケージ

math/bigパッケージは、Go言語で任意精度の算術演算を行うための機能を提供します。これは、標準の組み込み型（int, int64など）では扱えない、非常に大きな整数や浮動小数点数を扱う必要がある場合に不可欠です。例えば、暗号学、科学計算、金融アプリケーションなどで利用されます。Int型は、符号と数値の絶対値を内部的に表現し、必要に応じてメモリを動的に割り当てて任意の桁数を扱えるように設計されています。

最大公約数 (GCD: Greatest Common Divisor)

最大公約数（GCD）は、2つ以上の整数に共通する約数の中で最大のものです。例えば、12と18の最大公約数は6です。GCDの計算は、数論、暗号学、コンピュータサイエンスの様々な分野で基本的な操作として利用されます。

ユークリッドの互除法

ユークリッドの互除法は、2つの整数の最大公約数を効率的に計算するための古典的なアルゴリズムです。これは、gcd(a, b) = gcd(b, a mod b)という性質に基づいています。a mod bが0になるまでこの操作を繰り返し、最後に0でない剰余がGCDとなります。

バイナリGCDアルゴリズム (Steinのアルゴリズム)

バイナリGCDアルゴリズムは、ユークリッドの互除法とは異なり、除算や剰余演算を使用せず、ビットシフト、減算、偶奇判定のみで最大公約数を計算します。このアルゴリズムは、特に大きな整数に対して、除算が遅いプロセッサアーキテクチャや、任意精度演算において効率的であるとされています。

バイナリGCDアルゴリズムの基本的な考え方は以下の通りです。

gcd(0, n) = n
gcd(m, 0) = m
gcd(m, m) = m
mとnが両方偶数の場合: gcd(m, n) = 2 * gcd(m/2, n/2)
mが偶数、nが奇数の場合: gcd(m, n) = gcd(m/2, n)
mが奇数、nが偶数の場合: gcd(m, n) = gcd(m, n/2)
mとnが両方奇数の場合: gcd(m, n) = gcd((m-n)/2, n) (または gcd(m, (n-m)/2))

このアルゴリズムは、ビット演算に特化しているため、現代のコンピュータアーキテクチャで非常に高速に動作します。

`Int.abs`と`len(Int.abs)`

math/big.Int型は、内部的に数値の絶対値をWord型のスライス（abs []Word）として保持します。Wordは、プラットフォームのワードサイズ（例えば32ビットまたは64ビット）に対応する符号なし整数型です。 len(v.abs) == 0という条件は、vの絶対値が空のスライスであることを意味します。これは、vがゼロ（0）であることのmath/bigパッケージにおける内部的な表現です。

`trailingZeroBits()`

trailingZeroBits()メソッドは、数値の最下位ビットから連続するゼロの数を数えます。これは、バイナリGCDアルゴリズムにおいて、共通の2の因数を効率的に見つけて取り除くために使用されます。例えば、12 (1100_2)のtrailingZeroBits()は2です。

技術的詳細

binaryGCD関数は、math/big.Int型で表現された2つの任意精度整数aとbの最大公約数を計算します。この関数は、Knuthの「The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B」に記述されているバイナリGCDアルゴリズムを実装しています。

元のコードでは、まずuとvをaとbのコピーとして初期化し、最初のユークリッド互除法のようなステップ（switch文）で、uとvのサイズを近似的に揃えようとします。このステップは、aとbのどちらかが他方よりもはるかに大きい場合に、計算を効率化するためのものです。

問題は、この初期ステップの後、vがゼロになる可能性があることでした。例えば、aがbの倍数である場合、a.Mod(b)の結果がゼロになり、vがゼロに設定される可能性があります。バイナリGCDアルゴリズムの残りの部分は、通常、両方の入力が非ゼロであることを前提としています。vがゼロのままアルゴリズムを続行すると、trailingZeroBits()のような操作が不正な結果を返したり、論理エラーを引き起こしたりする可能性がありました。

修正は、この初期ステップの直後にvがゼロであるかどうかを明示的にチェックするものです。len(v.abs) == 0は、vがゼロであることを示すmath/big.Intの内部的な状態です。もしvがゼロであれば、gcd(u, 0) = uという数学的性質に基づき、uが最大公約数となるため、関数は直ちにuを返します。これにより、アルゴリズムの残りの部分が不正な入力で実行されることを防ぎ、常に正しい結果を保証します。

また、関数のコメントも「which must be positive」から「which both must be > 0」に変更されています。これは、入力が厳密に正であること（ゼロを含まない）を明確にするためのものです。バイナリGCDアルゴリズムは、通常、正の整数に対して定義されるため、このコメントの変更は関数の前提条件をより正確に反映しています。

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

--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -643,12 +643,13 @@ func (z *Int) GCD(x, y, a, b *Int) *Int {
 	return z
 }
 
-// binaryGCD sets z to the greatest common divisor of a and b, which must be
-// positive, and returns z.
+// binaryGCD sets z to the greatest common divisor of a and b, which both must
+// be > 0, and returns z.
 // See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B.
 func (z *Int) binaryGCD(a, b *Int) *Int {
 	u := z
 	v := new(Int)
+
 	// use one Euclidean iteration to ensure that u and v are approx. the same size
 	switch {
 	case len(a.abs) > len(b.abs):
@@ -662,6 +663,12 @@ func (z *Int) binaryGCD(a, b *Int) *Int {
 		v.Set(b)
 	}
 
+	// v might be 0 now
+	if len(v.abs) == 0 {
+		return u
+	}
+	// u > 0 && v > 0
+
 	// determine largest k such that u = u' << k, v = v' << k
 	k := u.abs.trailingZeroBits()
 	if vk := v.abs.trailingZeroBits(); vk < k {

コアとなるコードの解説

このコミットにおける主要な変更点は以下の2つです。

関数のコメントの修正:
```
-// binaryGCD sets z to the greatest common divisor of a and b, which must be
-// positive, and returns z.
+// binaryGCD sets z to the greatest common divisor of a and b, which both must
+// be > 0, and returns z.
```
これは、binaryGCD関数が受け入れる引数aとbの条件をより厳密に定義しています。元のコメントの「positive」（正）は、ゼロを含むか含まないか曖昧な場合がありますが、「> 0」（ゼロより大きい）と明記することで、入力が厳密に正の整数でなければならないことを明確にしています。これは、バイナリGCDアルゴリズムの数学的な前提条件と一致します。
ゼロ値のvに対する早期リターン処理の追加:
```
	// v might be 0 now
	if len(v.abs) == 0 {
		return u
	}
	// u > 0 && v > 0
```
このコードブロックは、初期のユークリッド互除法のようなステップ（switch文）の直後に追加されました。
- // v might be 0 now: このコメントは、直前の処理（switch文）によってvがゼロになる可能性があることを示唆しています。例えば、aがbの倍数である場合、a.Mod(b)の結果がゼロになり、vがゼロに設定されることがあります。
- if len(v.abs) == 0: これは、vがゼロであるかどうかをチェックする条件です。math/big.Intの内部表現において、絶対値のスライスabsの長さがゼロであることは、その整数がゼロであることを意味します。
- return u: もしvがゼロであれば、数学的にgcd(u, 0) = uが成り立つため、uが最大公約数となります。この早期リターンにより、vがゼロであるという不正な状態でバイナリGCDアルゴリズムの残りの部分が実行されることを防ぎ、関数の正確性と堅牢性を保証します。
- // u > 0 && v > 0: このコメントは、このチェックを通過した後、uとvの両方が厳密に正の整数であることが保証されることを示しています。これにより、その後のバイナリGCDアルゴリズムの主要なループが、その前提条件を満たした入力で実行されることが保証されます。

この修正は、binaryGCD関数が特定の入力（特に、最初のユークリッドステップで一方の数がゼロになるようなケース）に対して、常に正しく動作することを保証するための重要なバグ修正です。

参考にした情報源リンク

Donald E. Knuth, "The Art of Computer Programming, Volume 2: Seminumerical Algorithms", Third Edition. Addison-Wesley Professional, 1997. (特に Section 4.5.2, Algorithm B)
Binary GCD algorithm - Wikipedia: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
Go言語のソースコード (src/pkg/math/big/int.go)

comemo