Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

コミット

このコミットは、Go言語の標準ライブラリであるmath/bigパッケージ内のInt.GCD関数における入力値の検証ロジックを修正し、それに伴いGCD関数のテストを大幅に改善するものです。具体的には、Int.GCD関数が正の入力のみを期待しているにもかかわらず、ゼロの入力に対するハンドリングが不十分であった点を修正し、より堅牢なテストケースを追加しています。

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

https://github.com/golang/go/commit/10b88888f67ecda0b3dd86b91417cf9bfb20f2ed

元コミット内容

math/big: correctly test for positive inputs in Int.GCD

Also: better GCD tests.

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

変更の背景

math/bigパッケージのInt.GCD関数は、最大公約数（GCD）を計算する機能を提供します。この関数は、そのドキュメントにおいて、入力となるaとbが「両方とも> 0でなければならない」と明記されています。しかし、コミット前の実装では、この前提条件に違反する入力（特にゼロ）に対するハンドリングが不完全でした。具体的には、入力が負の数である場合にはz = x = y = 0と設定していましたが、ゼロである場合にはこのチェックが漏れていました。数学的なGCDの定義では、GCD(a, 0) = |a|、GCD(0, 0) = 0 となりますが、このInt.GCD関数の契約では、正の入力のみを想定しているため、契約に違反する入力（ゼロまたは負の数）に対しては、一貫して0を返すように修正する必要がありました。

また、既存のテストは、Int.GCD関数の様々なエッジケース、特にゼロや負の数といった不正な入力に対する網羅性が低いという問題がありました。任意精度整数を扱うmath/bigパッケージの特性上、非常に大きな数値に対するテストも重要であり、既存のテストフレームワークではその記述が煩雑でした。これらの背景から、Int.GCD関数の堅牢性を高め、テストの品質を向上させる必要がありました。

前提知識の解説

  • 最大公約数 (GCD: Greatest Common Divisor): 2つ以上の整数に共通する約数のうち、最大のものを指します。例えば、GCD(12, 18) = 6 です。GCDは通常、正の整数に対して定義されますが、負の整数やゼロに拡張されることもあります。このコミットで扱われるInt.GCD関数は、入力が正の整数であることを前提としています。

  • 拡張ユークリッドの互除法 (Extended Euclidean Algorithm): 2つの整数 a と b の最大公約数 d を求めるだけでなく、ax + by = d となる整数 x と y も求めるアルゴリズムです。この線形結合はベズーの等式（Bézout's identity）として知られています。Int.GCD関数は、このxとyも計算する機能を持っています。

  • Go言語のmath/bigパッケージ: Go言語の標準ライブラリの一部であり、任意精度（任意の大きさ）の整数（Int）、有理数（Rat）、浮動小数点数（Float）を扱うためのパッケージです。通常のint型やfloat64型では表現できない非常に大きな数値や、高い精度が要求される計算を行う際に使用されます。金融計算、暗号化、科学技術計算などで利用されます。

  • *big.Int.Sign()メソッド: *big.Int型のレシーバに対して呼び出され、その数値の符号を返します。

    • x > 0 の場合、+1
    • x < 0 の場合、-1
    • x == 0 の場合、0 を返します。このメソッドは、数値が正、負、またはゼロであるかを簡潔かつ正確に判定するために非常に有用です。

  • *big.Int.negフィールド: big.Int構造体の内部フィールドで、数値が負であるかどうかを示すブーリアン値です。このコミット以前は、負の数であるかどうかのチェックに直接このフィールドが使われていましたが、ゼロのケースを考慮していませんでした。

技術的詳細

このコミットの主要な変更点は、math/bigパッケージのInt.GCD関数における入力値の検証ロジックの修正と、それに伴うテストの強化です。

  1. Int.GCD関数の入力検証の修正:

    • 変更前: if a.neg || b.neg { ... }
      • この条件は、入力aまたはbが負の数である場合にのみ、GCDの結果を0に設定していました。しかし、Int.GCDのドキュメントでは「aとbは両方とも> 0でなければならない」と明記されており、0が入力された場合も不正な入力として扱う必要がありました。例えば、GCD(5, 0)のようなケースでは、数学的には5ですが、この関数の契約では許容されない入力であり、0を返すのが適切と判断されました。
    • 変更後: if a.Sign() <= 0 || b.Sign() <= 0 { ... }
      • a.Sign() <= 0 は「aが負の数またはゼロである」ことを意味します。同様に b.Sign() <= 0 は「bが負の数またはゼロである」ことを意味します。
      • この修正により、aまたはbが負の数であるか、またはゼロである場合に、GCDの結果（z）および拡張ユークリッドの係数（x, y）がすべて0に設定されるようになりました。これにより、関数の契約と実装の整合性が保たれ、不正な入力に対する挙動が一貫して定義されました。

  2. int_test.goにおけるテストの改善:

    • gcdTests構造体の変更: 以前はint64型のa, b, d, x, yを使用してテストケースを定義していましたが、これは任意精度整数を扱うmath/bigパッケージのテストとしては不十分でした。int64では表現できない非常に大きな数値や、特定の性質を持つ数値（例: 1や非常に大きな素数）に対するテストが困難でした。
      • 変更後は、string型でこれらの値を定義するようになり、new(Int).SetString(value, 0)メソッドを使って任意精度の数値をテストケースに含めることが可能になりました。これにより、テストの表現力が大幅に向上し、より現実的で網羅的なテストが可能になりました。
    • 新しいテストケースの追加:
      • a <= 0 || b <= 0 の条件を満たす入力（ゼロや負の数）に対するテストケースが多数追加されました。これにより、Int.GCD関数の修正が正しく機能し、不正な入力に対して期待通りの0が返されるかどうかが検証されます。
      • 非常に大きな数値に対するテストケースも追加され、任意精度演算の正確性が確認されます。
      • binaryGCD（内部的に使用される可能性のあるGCDアルゴリズム）の早期終了条件をテストするケースも追加され、内部実装の堅牢性も考慮されています。
    • testGcdヘルパー関数の導入:
      • テストロジックの重複を避けるため、testGcdという新しいヘルパー関数が導入されました。この関数は、期待されるGCD、x、y、入力a、bの*big.Int型ポインタを受け取り、実際のGCD関数の呼び出しと結果の検証を行います。これにより、テストコードの記述が簡潔になり、可読性と保守性が向上しました。
      • このヘルパー関数は、xやyがnilである場合（つまり、拡張ユークリッドの係数を計算しない場合）のテストも容易に行えるように設計されています。これは、GCD関数のxとy引数がオプションであるため、その挙動を網羅的にテストするために重要です。
    • テスト実行ロジックの改善: TestGcd関数内では、gcdTestsの各テストケースに対して、testGcdヘルパー関数を様々な引数の組み合わせで呼び出しています。特に、xやyの有無を様々に組み合わせてテストを実行するようになりました。これにより、GCD関数の様々な呼び出しパターンが網羅的にテストされ、関数の柔軟な使用方法が適切に検証されています。

これらの変更により、Int.GCD関数の堅牢性が向上し、特に不正な入力に対する挙動が明確かつ正確になりました。また、テストの網羅性が大幅に向上したことで、将来的な変更に対する回帰テストの信頼性も高まりました。

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

src/pkg/math/big/int.go

--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -581,12 +581,12 @@ func (z *Int) Exp(x, y, m *Int) *Int {
 	return z
 }
 
-// GCD sets z to the greatest common divisor of a and b, which must be
-// positive numbers, and returns z.
+// GCD sets z to the greatest common divisor of a and b, which both must
+// be > 0, and returns z.
 // If x and y are not nil, GCD sets x and y such that z = a*x + b*y.
-// If either a or b is not positive, GCD sets z = x = y = 0.
+// If either a or b is <= 0, GCD sets z = x = y = 0.
 func (z *Int) GCD(x, y, a, b *Int) *Int {
-\tif a.neg || b.neg {\n+\tif a.Sign() <= 0 || b.Sign() <= 0 {\n \t\tz.SetInt64(0)\n \t\tif x != nil {\n \t\t\tx.SetInt64(0)

src/pkg/math/big/int_test.go

--- a/src/pkg/math/big/int_test.go
+++ b/src/pkg/math/big/int_test.go
@@ -818,14 +818,12 @@ func TestExp(t *testing.T) {
 }
 
 func checkGcd(aBytes, bBytes []byte) bool {
-\ta := new(Int).SetBytes(aBytes)\n-\tb := new(Int).SetBytes(bBytes)\n-\n \tx := new(Int)\n \ty := new(Int)\n-\td := new(Int)\n+\ta := new(Int).SetBytes(aBytes)\n+\tb := new(Int).SetBytes(bBytes)\n \n-\td.GCD(x, y, a, b)\n+\td := new(Int).GCD(x, y, a, b)\n \tx.Mul(x, a)\n \ty.Mul(y, b)\n \tx.Add(x, y)\n@@ -834,39 +832,70 @@ func checkGcd(aBytes, bBytes []byte) bool {
 }
 
 var gcdTests = []struct {
-\ta, b    int64\n-\td, x, y int64\n+\td, x, y, a, b string\n }{\n-\t{120, 23, 1, -9, 47},\n-}\n-\n-func TestGcd(t *testing.T) {\n-\tfor i, test := range gcdTests {\n-\t\ta := NewInt(test.a)\n-\t\tb := NewInt(test.b)\n-\n-\t\tx := new(Int)\n-\t\ty := new(Int)\n-\t\td := new(Int)\n-\n-\t\texpectedX := NewInt(test.x)\n-\t\texpectedY := NewInt(test.y)\n-\t\texpectedD := NewInt(test.d)\n-\n-\t\td.GCD(x, y, a, b)\n+\t// a <= 0 || b <= 0\n+\t{\"0\", \"0\", \"0\", \"0\", \"0\"},\n+\t{\"0\", \"0\", \"0\", \"0\", \"7\"},\n+\t{\"0\", \"0\", \"0\", \"11\", \"0\"},\n+\t{\"0\", \"0\", \"0\", \"-77\", \"35\"},\n+\t{\"0\", \"0\", \"0\", \"64515\", \"-24310\"},\n+\t{\"0\", \"0\", \"0\", \"-64515\", \"-24310\"},\n+\n+\t{\"1\", \"-9\", \"47\", \"120\", \"23\"},\n+\t{\"7\", \"1\", \"-2\", \"77\", \"35\"},\n+\t{\"935\", \"-3\", \"8\", \"64515\", \"24310\"},\n+\t{\"935000000000000000\", \"-3\", \"8\", \"64515000000000000000\", \"24310000000000000000\"},\n+\t{\"1\", \"-221\", \"22059940471369027483332068679400581064239780177629666810348940098015901108344\", \"98920366548084643601728869055592650835572950932266967461790948584315647051443\", \"991\"},\n+\n+\t// test early exit (after one Euclidean iteration) in binaryGCD\n+\t{\"1\", \"\", \"\", \"1\", \"98920366548084643601728869055592650835572950932266967461790948584315647051443\"},\n+}\n+\n+func testGcd(t *testing.T, d, x, y, a, b *Int) {\n+\tvar X *Int\n+\tif x != nil {\n+\t\tX = new(Int)\n+\t}\n+\tvar Y *Int\n+\tif y != nil {\n+\t\tY = new(Int)\n+\t}\n \n-\t\tif expectedX.Cmp(x) != 0 ||\n-\t\t\texpectedY.Cmp(y) != 0 ||\n-\t\t\texpectedD.Cmp(d) != 0 {\n-\t\t\tt.Errorf(\"#%d got (%s %s %s) want (%s %s %s)\", i, x, y, d, expectedX, expectedY, expectedD)\n-\t\t}\n+\tD := new(Int).GCD(X, Y, a, b)\n+\tif D.Cmp(d) != 0 {\n+\t\tt.Errorf(\"GCD(%s, %s): got d = %s, want %s\", a, b, D, d)\n+\t}\n+\tif x != nil && X.Cmp(x) != 0 {\n+\t\tt.Errorf(\"GCD(%s, %s): got x = %s, want %s\", a, b, X, x)\n+\t}\n+\tif y != nil && Y.Cmp(y) != 0 {\n+\t\tt.Errorf(\"GCD(%s, %s): got y = %s, want %s\", a, b, Y, y)\n+\t}\n \n-\t\td.binaryGCD(a, b)\n+\t// binaryGCD requires a > 0 && b > 0\n+\tif a.Sign() <= 0 || b.Sign() <= 0 {\n+\t\treturn\n+\t}\n \n-\t\tif expectedD.Cmp(d) != 0 {\n-\t\t\tt.Errorf(\"#%d got (%s) want (%s)\", i, d, expectedD)\n-\t\t}\n+\tD.binaryGCD(a, b)\n+\tif D.Cmp(d) != 0 {\n+\t\tt.Errorf(\"binaryGcd(%s, %s): got d = %s, want %s\", a, b, D, d)\n+\t}\n+}\n \n+func TestGcd(t *testing.T) {\n+\tfor _, test := range gcdTests {\n+\t\td, _ := new(Int).SetString(test.d, 0)\n+\t\tx, _ := new(Int).SetString(test.x, 0)\n+\t\ty, _ := new(Int).SetString(test.y, 0)\n+\t\ta, _ := new(Int).SetString(test.a, 0)\n+\t\tb, _ := new(Int).SetString(test.b, 0)\n+\n+\t\ttestGcd(t, d, nil, nil, a, b)\n+\t\ttestGcd(t, d, x, nil, a, b)\n+\t\ttestGcd(t, d, nil, y, a, b)\n+\t\ttestGcd(t, d, x, y, a, b)\n \t}\n \n \tquick.Check(checkGcd, nil)\n```

## コアとなるコードの解説

`src/pkg/math/big/int.go` の変更は、`Int.GCD`関数の冒頭にある入力検証ロジックを修正しています。
*   変更前は `a.neg || b.neg` という条件で、入力 `a` または `b` が負の数である場合にのみ、GCDの結果を `0` に設定していました。
*   変更後は `a.Sign() <= 0 || b.Sign() <= 0` となっています。これは、`a` または `b` が負の数であるか、あるいはゼロである場合に、GCDの結果を `0` に設定することを意味します。これにより、関数のドキュメントで「`a`と`b`は両方とも`> 0`でなければならない」と明記されている契約に、より厳密に準拠するようになりました。`Int.Sign()`メソッドを使用することで、数値の符号を正確に判定し、ゼロの場合も適切に処理できるようになります。

`src/pkg/math/big/int_test.go` の変更は、`Int.GCD`関数のテストを大幅に改善しています。
*   `gcdTests`構造体は、`int64`から`string`型に変わり、任意精度の数値をテストできるようになりました。これにより、非常に大きな数値や、ゼロ、負の数といったエッジケースをテストデータとして直接記述できるようになります。
*   `testGcd`という新しいヘルパー関数が導入されました。この関数は、テストケースの各要素（期待されるGCD、x、y、入力a、b）を`*Int`型で受け取り、実際の`GCD`関数の呼び出しと結果の検証を行います。これにより、テストコードの重複が減り、可読性と保守性が向上します。
*   `TestGcd`関数内では、`testGcd`ヘルパー関数を様々な引数の組み合わせで呼び出しています。特に、`x`や`y`が`nil`の場合（つまり、拡張ユークリッドの係数を計算しない場合）のテストも網羅されており、`Int.GCD`関数の柔軟な使用方法が適切にテストされています。
*   `checkGcd`ヘルパー関数も、`Int`オブジェクトの初期化方法が変更され、より簡潔になっています。

これらの変更は、`Int.GCD`関数の正確性と堅牢性を高めるとともに、テストの品質を向上させ、将来的なコードの変更に対する安全性を確保しています。

## 関連リンク

*   Go言語 `math/big` パッケージのドキュメント: [https://pkg.go.dev/math/big](https://pkg.go.dev/math/big)
*   最大公約数 (GCD) - Wikipedia: [https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0](https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0)
*   拡張ユークリッドの互除法 - Wikipedia: [https://ja.wikipedia.org/wiki/%E6%8B%A1%E5%BC%B5%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95](https://ja.wikipedia.org/wiki/%E6%8B%A1%E5%BC%B5%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95)

## 参考にした情報源リンク

*   Go言語の公式ドキュメント
*   Wikipedia (最大公約数、拡張ユークリッドの互除法)