[インデックス 13339] ファイルの概要
このコミットは、Go言語の標準ライブラリ math/big パッケージにおいて、多倍長整数（Int型）の最大公約数（GCD: Greatest Common Divisor）計算に「バイナリGCDアルゴリズム」を導入するものです。これにより、既存のユークリッドの互除法に基づく実装と比較して、特に大きな数値に対するGCD計算のパフォーマンスが大幅に向上しています。
コミット
commit 38735b957c2e7d1f93021943dafc5b931b9ccab3
Author: Christopher Swenson <cswenson@google.com>
Date: Wed Jun 13 09:31:20 2012 -0700
math/big: Implemented binary GCD algorithm
benchmark old ns/op new ns/op delta
BenchmarkGCD10x10 4383 2126 -51.49%
BenchmarkGCD10x100 5612 2124 -62.15%
BenchmarkGCD10x1000 8843 2622 -70.35%
BenchmarkGCD10x10000 17025 6576 -61.37%
BenchmarkGCD10x100000 118985 48130 -59.55%
BenchmarkGCD100x100 45328 11683 -74.23%
BenchmarkGCD100x1000 50141 12678 -74.72%
BenchmarkGCD100x10000 110314 26719 -75.78%
BenchmarkGCD100x100000 630000 156041 -75.23%
BenchmarkGCD1000x1000 654809 137973 -78.93%
BenchmarkGCD1000x10000 985683 159951 -83.77%
BenchmarkGCD1000x100000 4920792 366399 -92.55%
BenchmarkGCD10000x10000 16848950 3732062 -77.85%
BenchmarkGCD10000x100000 55401500 4675876 -91.56%
BenchmarkGCD100000x100000 1126775000 258951800 -77.02%
R=gri, rsc, bradfitz, remyoudompheng, mtj
CC=golang-dev
https://golang.org/cl/6305065
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/38735b957c2e7d1f93021943dafc5b931b9ccab3
元コミット内容
このコミットの主な内容は、math/big パッケージにおける多倍長整数の最大公約数 (GCD) 計算アルゴリズムを、従来のユークリッドの互除法から「バイナリGCDアルゴリズム」へ変更することです。これにより、特に大きな数値のGCD計算において顕著なパフォーマンス改善が達成されています。コミットメッセージには、様々なサイズの数値ペアに対するベンチマーク結果が示されており、最大で90%以上の高速化が確認できます。
変更の背景
多倍長整数演算は、暗号技術や科学技術計算など、非常に大きな整数を扱う必要がある分野で不可欠です。これらの計算において、GCDは頻繁に利用される基本的な操作の一つです。従来のユークリッドの互除法は、除算操作を多用するため、多倍長整数においてはそのコストが非常に高くなります。
バイナリGCDアルゴリズムは、除算や剰余演算の代わりに、シフト演算、減算、および偶奇性のチェックといった、より高速なビット演算を主に使用します。これにより、特にハードウェアレベルでの最適化が期待でき、多倍長整数のようなソフトウェアで実装される数値演算において、パフォーマンス上の大きなボトルネックを解消することが可能になります。
この変更の背景には、math/big パッケージの性能向上という明確な目標があり、特にGCDのような基本的な操作の効率化は、そのパッケージを利用する広範なアプリケーションの性能に直接貢献します。
前提知識の解説
最大公約数 (GCD: Greatest Common Divisor)
最大公約数とは、2つ以上の整数に共通する約数の中で最大のものです。例えば、12と18の最大公約数は6です。
ユークリッドの互除法
ユークリッドの互除法は、2つの整数の最大公約数を効率的に求めるためのアルゴリズムです。これは、gcd(a, b) = gcd(b, a mod b) という性質に基づいています。a mod b が0になるまでこの操作を繰り返し、その時の b が最大公約数となります。このアルゴリズムは数学的に非常にエレガントですが、多倍長整数においては mod (剰余) 演算が計算コストの高い操作となります。
バイナリGCDアルゴリズム (Stein's Algorithm)
バイナリGCDアルゴリズム（またはスタインのアルゴリズム）は、ユークリッドの互除法とは異なり、除算や剰余演算を一切使用せず、ビットシフト（2による除算）と減算、偶奇性のチェックのみで最大公約数を計算します。このアルゴリズムは以下の性質に基づいています。
gcd(0, n) = ngcd(m, n) = gcd(n, 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)（m > nの場合。n > mならgcd(m, (n-m)/2)）
これらの性質を利用することで、除算を伴わない高速なGCD計算が可能になります。特に多倍長整数では、除算は非常にコストがかかるため、このアルゴリズムは大きな利点をもたらします。
math/big パッケージ
Go言語の math/big パッケージは、任意精度の算術演算を提供するパッケージです。Int型は任意のサイズの整数を表現でき、Rat型は有理数を表現します。これらの型は、標準のGoの組み込み型では扱えない非常に大きな数や、精度が要求される計算に用いられます。
技術的詳細
このコミットでは、math/big パッケージの Int 型に binaryGCD という新しいメソッドが追加されています。既存の GCD メソッドは、引数 x と y が nil の場合にこの新しい binaryGCD メソッドを呼び出すように変更されています。これは、拡張ユークリッドの互除法（x と y が nil でない場合に係数を計算する）と、単にGCDを計算する場合（x と y が nil の場合）で処理を分岐させるためです。
binaryGCD メソッドの実装は、Knuthの「The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B」に記述されているバイナリGCDアルゴリズムに基づいています。
主要なステップは以下の通りです。
-
初期化とサイズ調整:
uとvを初期化します。最初にユークリッドの互除法を1回だけ適用し、uとvのサイズを近似的に同じにします。これにより、アルゴリズムの初期段階での効率が向上します。uとvのうち、小さい方をuに、大きい方をvの剰余に設定します。
-
共通の2の因数を抽出:
uとvの両方から、共通して含まれる2の因数（末尾のゼロビットの数）をkとして抽出します。これはtrailingZeroBits()メソッドで計算されます。uとvをそれぞれ2^kで右シフト（除算）し、両方を奇数にします。このkは最終的な結果に乗算されます。
-
メインループ:
tという一時変数を導入し、uまたは-vのいずれかに初期化します。uが奇数であればt = -v、そうでなければt = uとします。tがゼロになるまでループを続けます。- ループ内で
tを2で割り続け（trailingZeroBits()を利用して右シフト）、奇数にします。 - もし
tが負であれば、v = -tとし、tを正に変換します。 - もし
tが正であれば、u = tとします。 - 最後に
t = u - vを計算し、次のイテレーションに備えます。
-
結果の調整:
- ループが終了すると、
uには共通の奇数部分のGCDが格納されています。 - 最終結果は
uをkビット左シフト（2^kを乗算）したものです。
- ループが終了すると、
math/big/rat.go ファイルでは、有理数 Rat の正規化処理 (norm メソッド) において、分母と分子のGCDを計算する際に、従来の gcd 関数（ユークリッドの互除法）の代わりに、新しく導入された NewInt(0).binaryGCD(&z.a, &z.b) を使用するように変更されています。これにより、有理数の正規化も高速化されます。
ベンチマーク結果は、この変更が非常に効果的であったことを明確に示しています。特に大きな数値（例: BenchmarkGCD1000x100000 や BenchmarkGCD100000x100000）では、90%以上の実行時間削減が達成されており、これは多倍長整数演算の性能にとって極めて重要な改善です。
コアとなるコードの変更箇所
src/pkg/math/big/int.go
func (z *Int) GCD(x, y, a, b *Int) *Int {
// ... (既存のコード) ...
if x == nil && y == nil {
return z.binaryGCD(a, b)
}
// ... (既存のコード) ...
}
// binaryGCD sets z to the greatest common divisor of a and b, which must be
// positive, 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):
u.Set(b)
v.Rem(a, b)
case len(a.abs) < len(b.abs):
u.Set(a)
v.Rem(b, a)
default:
u.Set(a)
v.Set(b)
}
// determine largest k such that u = u' << k, v = v' << k
k := u.abs.trailingZeroBits()
if vk := v.abs.trailingZeroBits(); vk < k {
k = vk
}
u.Rsh(u, k)
v.Rsh(v, k)
// determine t (we know that u > 0)
t := new(Int)
if u.abs[0]&1 != 0 {
// u is odd
t.Neg(v)
} else {
t.Set(u)
}
for len(t.abs) > 0 {
// reduce t
t.Rsh(t, t.abs.trailingZeroBits())
if t.neg {
v.Neg(t)
} else {
u.Set(t)
}
t.Sub(u, v)
}
return u.Lsh(u, k)
}
src/pkg/math/big/rat.go
func (z *Rat) norm() *Rat {
switch {
// ... (既存のコード) ...
default:
- if f := gcd(z.a.abs, z.b.abs); f.cmp(natOne) != 0 {
- z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f)
- z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f)
- if z.b.abs.cmp(natOne) == 0 {
- // z is int - normalize denominator
- z.b.abs = z.b.abs.make(0)
- }
+ neg := z.a.neg
+ z.a.neg = false
+ z.b.neg = false
+ if f := NewInt(0).binaryGCD(&z.a, &z.b); f.Cmp(intOne) != 0 {
+ z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f.abs)
+ z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f.abs)
+ if z.b.abs.cmp(natOne) == 0 {
+ // z is int - normalize denominator
+ z.b.abs = z.b.abs.make(0)
+ }
+ }
+ z.a.neg = neg
}
return z
}
コアとなるコードの解説
src/pkg/math/big/int.go の変更
-
GCDメソッドの変更:GCDメソッドは、xとyの両方がnilの場合に、新しく追加されたbinaryGCDメソッドを呼び出すように変更されました。これは、拡張ユークリッドの互除法（xとyが非nilの場合）と、単にGCDを計算する（xとyがnilの場合）という2つの異なるユースケースを効率的に処理するための分岐です。
-
binaryGCDメソッドの追加:- この新しいメソッドは、2つの正の多倍長整数
aとbの最大公約数を計算し、結果をzに設定して返します。 - 初期のユークリッド反復:
uとvのサイズを近似的に同じにするために、最初に1回のユークリッドの互除法（剰余演算）が適用されます。これは、アルゴリズムの初期収束を助けるための最適化です。 - 共通の2の因数の抽出:
u.abs.trailingZeroBits()とv.abs.trailingZeroBits()を使用して、uとvの両方から共通の2の因数（末尾のゼロビットの数）kを見つけます。その後、uとvをそれぞれkビット右シフト（2^kで除算）して、両方を奇数にします。このkは最終的な結果に乗算されます。 - メインループ:
tはuまたは-vのいずれかに初期化されます。uが奇数であればt = -v、そうでなければt = uとなります。- ループは
tがゼロになるまで続きます。 - ループの各ステップで、
tはt.abs.trailingZeroBits()を使って末尾のゼロビットを取り除き、奇数に正規化されます。 tの符号に基づいて、uまたはvのいずれかがtの絶対値に更新されます。- 最後に、
t = u - vが計算され、次のイテレーションに備えます。このu - vの結果は、必ず偶数になります（奇数 - 奇数 = 偶数）。
- 最終結果: ループが終了すると、
uにはaとbの奇数部分のGCDが格納されています。最終的なGCDは、このuをkビット左シフト（2^kを乗算）することで得られます。
- この新しいメソッドは、2つの正の多倍長整数
src/pkg/math/big/rat.go の変更
normメソッドの変更:- 有理数
Ratを正規化するnormメソッド内で、分母と分子の最大公約数を計算するために、従来のgcd関数（ユークリッドの互除法の実装）の呼び出しが削除されました。 - 代わりに、
NewInt(0).binaryGCD(&z.a, &z.b)を使用して、新しいバイナリGCDアルゴリズムが呼び出されるようになりました。これにより、有理数の正規化処理も高速化されます。 z.a.neg = falseとz.b.neg = falseは、binaryGCDが正の数に対して動作することを保証するために、符号を一時的に無視している部分です。計算後に元の符号negをz.a.negに戻しています。
- 有理数
これらの変更により、math/big パッケージにおけるGCD計算のパフォーマンスが大幅に向上し、その恩恵は Rat 型の正規化など、GCDを利用する他の機能にも波及しています。
関連リンク
- Go言語
math/bigパッケージのドキュメント: https://pkg.go.dev/math/big - Go言語の変更リスト (CL): https://golang.org/cl/6305065
参考にした情報源リンク
- Donald Knuth, "The Art of Computer Programming, Volume 2: Seminumerical Algorithms", Section 4.5.2, Algorithm B (Binary GCD algorithm).
- Wikipedia: Binary GCD algorithm: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
- Wikipedia: Euclidean algorithm: https://en.wikipedia.org/wiki/Euclidean_algorithm