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

このコミットは、Go言語の math/big パッケージにおける nat 型（多倍長自然数）の操作に関する改善です。具体的には、数値の最下位ビットから連続するゼロの数を効率的に計算する nat.trailingZeroBits メソッドが追加され、それに伴い既存のコード（特に powersOfTwoDecompose 関数）が簡素化されました。この変更は、将来的に binaryGCD（バイナリGCDアルゴリズム）の実装を簡素化することを目的としています。

コミット

commit 014d036d84494f6613174ebe1bf118469a216b52
Author: Robert Griesemer <gri@golang.org>
Date:   Fri Jun 8 13:00:49 2012 -0700

    math/big: added nat.trailingZeroBits, simplified some code
    
    Will simplify implementation of binaryGCD.
    
    R=rsc, cswenson
    CC=golang-dev
    https://golang.org/cl/6299064

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

https://github.com/golang/go/commit/014d036d84494f6613174ebe1bf118469a216b52

元コミット内容

math/big: added nat.trailingZeroBits, simplified some code

Will simplify implementation of binaryGCD.

R=rsc, cswenson
CC=golang-dev
https://golang.org/cl/6299064

変更の背景

このコミットの主な背景は、math/big パッケージ内で多倍長整数に対する binaryGCD（バイナリ最大公約数）アルゴリズムの実装をより効率的かつ簡潔にするための準備です。binaryGCD アルゴリズムは、ユークリッドの互除法とは異なり、除算や剰余演算の代わりにビットシフトと減算を用いることで、特に大きな数値に対して高速なGCD計算を可能にします。このアルゴリズムでは、数値の末尾のゼロビットの数を頻繁に計算する必要があるため、trailingZeroBits のような効率的な関数が不可欠です。

既存の powersOfTwoDecompose 関数は、数値 x を q * 2^k の形式に分解するもので、この k を求める過程で trailingZeroBits の概念が使われていました。しかし、nat 型全体に対する trailingZeroBits メソッドを直接提供することで、このような分解処理をより汎用的に、かつ他の場所でも再利用可能な形で提供できるようになります。これにより、コードの重複を避け、可読性を向上させ、最終的に binaryGCD の実装を簡素化できるという意図があります。

前提知識の解説

math/big パッケージ

Go言語の math/big パッケージは、任意精度の算術演算を提供する標準ライブラリです。通常の int や int64 などの組み込み型では扱えない非常に大きな整数や、高い精度が求められる浮動小数点数、有理数を扱うために使用されます。このパッケージは、暗号学、科学計算、金融アプリケーションなど、正確な数値計算が不可欠な分野で広く利用されています。

nat 型

math/big パッケージにおける nat 型は、符号なしの多倍長自然数（非負整数）を表す内部的な型です。これは []Word のエイリアスとして定義されており、Word 型の配列として数値を表現します。Word はプラットフォームのワードサイズ（32ビットまたは64ビット）に応じた符号なし整数型（uint32 または uint64）です。例えば、64ビットシステムでは Word は uint64 となり、nat は []uint64 となります。数値はリトルエンディアン形式で格納されることが一般的です。

Word 型

Word 型は、math/big パッケージ内で多倍長整数を構成する「桁」の単位となる型です。Goの uint 型と同様に、実行環境のCPUアーキテクチャに依存して32ビットまたは64ビットの符号なし整数として定義されます。この型は、ビット演算や基本的な算術演算の効率を最大化するために使用されます。

trailingZeroBits (末尾ゼロビット)

trailingZeroBits は、与えられた数値の最下位ビットから連続するゼロの数を数える関数です。例えば、バイナリ表現で ...1000 のような数値の場合、末尾のゼロビットは3つです。この操作は、ビット演算を多用するアルゴリズム（例: GCD、ビットマップ操作）で非常に重要になります。

このコミットで言及されている trailingZeroBits の実装は、De Bruijnシーケンスに基づくアルゴリズムを使用しています。これは、特定の定数とビットシフト、テーブルルックアップを組み合わせることで、非常に高速に末尾ゼロビット数を計算する方法です。Knuthの著書「The Art of Computer Programming」のVolume 4, Section 7.3.1で詳細に解説されています。

binaryGCD (バイナリ最大公約数)

binaryGCD は、2つの非負整数の最大公約数（GCD）を計算するアルゴリズムです。ユークリッドの互除法が除算と剰余演算に依存するのに対し、binaryGCD はビットシフト、減算、および偶奇性のチェックのみを使用します。これにより、特にハードウェアレベルでのビット演算が高速な環境や、非常に大きな数値を扱う場合に効率的です。アルゴリズムの基本的なステップは以下の通りです。

1. 両方の数が偶数であれば、両方を2で割り、結果に2を掛ける（GCD(a, b) = 2 * GCD(a/2, b/2)）。
2. 片方が偶数であれば、その数を2で割る（GCD(a, b) = GCD(a/2, b)）。
3. 両方が奇数であれば、大きい方から小さい方を引き、結果を2で割る（GCD(a, b) = GCD((a-b)/2, b)）。
4. いずれかの数が0になるまで繰り返す。0でない方の数がGCDとなる。

このアルゴリズムでは、ステップ1と2で末尾のゼロビットを効率的に除去する（つまり2で割る）操作が頻繁に発生するため、trailingZeroBits のような関数が性能に大きく寄与します。

技術的詳細

このコミットの核となる技術的変更は、math/big パッケージの nat 型に trailingZeroBits メソッドを追加し、それを利用して既存の powersOfTwoDecompose 関数を削除し、その機能をより効率的な方法で置き換えた点です。

nat.trailingZeroBits() メソッドの追加

新しく追加された func (x nat) trailingZeroBits() uint メソッドは、多倍長自然数 x の最下位ビットから連続するゼロの数を uint 型で返します。この実装は、まず nat 型の配列 x を走査し、最初の非ゼロの Word 要素を見つけます。

func (x nat) trailingZeroBits() uint {
	if len(x) == 0 {
		return 0
	}
	var i uint
	for x[i] == 0 { // 最初の非ゼロのWord要素を探す
		i++
	}
	// x[i] != 0
	return i*_W + trailingZeroBits(x[i]) // ゼロのWordの数 * Wordのビット数 + 最初の非ゼロWordの末尾ゼロビット数
}

このメソッドは、以下のロジックで動作します。

1. nat 型 x が空（長さ0）の場合、末尾ゼロビットは0とします。
2. x の各 Word 要素をインデックス i から順にチェックします。
3. x[i] が 0 である限り i をインクリメントします。これは、数値の最下位から連続するゼロの Word の数を数えていることになります。
4. 最初の非ゼロの Word 要素 x[i] が見つかったら、それまでのゼロの Word の総ビット数 (i * _W、ここで _W は Word のビット幅、通常32または64) に、その非ゼロの Word (x[i]) 自体の末尾ゼロビット数 (trailingZeroBits(x[i])) を加算して返します。

このアプローチにより、多倍長整数全体の末尾ゼロビット数を効率的に計算できます。

powersOfTwoDecompose 関数の削除と置き換え

以前は、nat 型の数値 x を q * 2^k の形式に分解する powersOfTwoDecompose 関数が存在しました。この関数は、x の末尾のゼロビットの数を数え、それに基づいて q と k を計算していました。

// 削除されたコードの概要
func (x nat) powersOfTwoDecompose() (q nat, k int) {
    // ...
    i := 0
    for x[i] == 0 {
        i++
    }
    n := trailingZeroBits(x[i]) // x[i] != 0
    // ...
    k = i*_W + n
    // ...
}

このコミットでは、nat.trailingZeroBits() メソッドが導入されたため、powersOfTwoDecompose は不要となり削除されました。その機能は、math/big パッケージ内の probablyPrime 関数で直接 nat.trailingZeroBits() と nat.shr (右シフト) を組み合わせて実現されるようになりました。

具体的には、probablyPrime 関数内でミラー・ラビン素数判定法の一部として nm1 = q * 2^k の形式で nm1 (n-1) を分解する必要がある箇所で、以下のように変更されました。

変更前:

	nm1 := nat(nil).sub(n, natOne)
	// 1<<k * q = nm1;
	q, k := nm1.powersOfTwoDecompose()

変更後:

	nm1 := nat(nil).sub(n, natOne)
	// determine q, k such that nm1 = q << k
	k := nm1.trailingZeroBits() // 新しいメソッドを使用
	q := nat(nil).shr(nm1, k)   // 右シフトでqを計算

この変更により、powersOfTwoDecompose という特定の目的のための関数が削除され、より汎用的な nat.trailingZeroBits() と nat.shr を組み合わせることで、同じ機能がより簡潔かつ明確に表現されるようになりました。これは、コードのモジュール性と再利用性を高める良い例です。

trailingZeroBits(Word) の戻り値型の変更

既存の func trailingZeroBits(x Word) int 関数は、Word 型の末尾ゼロビット数を int で返していました。このコミットでは、その戻り値型が uint に変更されました。

--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -993,10 +993,9 @@ var deBruijn64Lookup = []byte{
 	54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
 }
 
-// trailingZeroBits returns the number of consecutive zero bits on the right
-// side of the given Word.
-// See Knuth, volume 4, section 7.3.1
-func trailingZeroBits(x Word) int {
+// trailingZeroBits returns the number of consecutive least significant zero
+// bits of x.
+func trailingZeroBits(x Word) uint {
 	// x & -x leaves only the right-most bit set in the word. Let k be the
 	// index of that bit. Since only a single bit is set, the value is two
 	// to the power of k. Multiplying by a power of two is equivalent to
@@ -1005,11 +1004,12 @@ func trailingZeroBits(x Word) int {
 	// Therefore, if we have a left shifted version of this constant we can
 	// find by how many bits it was shifted by looking at which six bit
 	// substring ended up at the top of the word.
+\t// (Knuth, volume 4, section 7.3.1)
 \tswitch _W {\n \tcase 32:\n-\t\treturn int(deBruijn32Lookup[((x&-x)*deBruijn32)>>27])\n+\t\treturn uint(deBruijn32Lookup[((x&-x)*deBruijn32)>>27])\n \tcase 64:\n-\t\treturn int(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58])\n+\t\treturn uint(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58])\n \tdefault:\
 \t\tpanic(\"Unknown word size\")
 \t}\n@@ -1017,6 +1017,20 @@ func trailingZeroBits(x Word) int {
 	return 0
 }

この変更は、ビット数という概念が通常非負であるため、より適切な uint 型を使用するように修正されたものです。これにより、型の一貫性が保たれ、潜在的な負の値の扱いに関する混乱がなくなります。

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

src/pkg/math/big/nat.go

• func (x nat) string(charset string) string 内の trailingZeroBits(b) の型キャスト uint() が削除されました。これは trailingZeroBits の戻り値型が uint に変更されたためです。
• func trailingZeroBits(x Word) int のシグネチャが func trailingZeroBits(x Word) uint に変更され、内部の戻り値も uint にキャストされるようになりました。
• 新しいメソッド func (x nat) trailingZeroBits() uint が追加されました。
• func (x nat) powersOfTwoDecompose() (q nat, k int) 関数が完全に削除されました。
• func (n nat) probablyPrime(reps int) bool 関数内で、nm1 の分解ロジックが powersOfTwoDecompose の呼び出しから、新しく追加された nm1.trailingZeroBits() と nat(nil).shr(nm1, k) の組み合わせに置き換えられました。
• probablyPrime 内のループ変数 j の型が int から uint に変更されました。

src/pkg/math/big/nat_test.go

• TestTrailingZeroBits 関数が大幅に修正され、Word 型だけでなく、新しく追加された nat.trailingZeroBits() メソッドのテストも含まれるようになりました。
  • Word 型のテストでは、x := Word(1) から開始し、左シフトしながら末尾ゼロビット数を検証するようになりました。
  • nat 型のテストでは、natOne から開始し、左シフトしながら nat.trailingZeroBits() の結果を検証するようになりました。

コアとなるコードの解説

src/pkg/math/big/nat.go の変更点

1. trailingZeroBits(Word) の戻り値型変更と利用箇所の修正:

   • func trailingZeroBits(x Word) int が func trailingZeroBits(x Word) uint に変更されました。これは、末尾ゼロビット数が非負の値であるため、より適切な uint 型を使用するようにしたものです。
   • これに伴い、func (x nat) string 内で trailingZeroBits(b) の結果を uint にキャストしていた部分が不要になり、shift := trailingZeroBits(b) と直接代入できるようになりました。

2. nat.trailingZeroBits() メソッドの追加:

   // trailingZeroBits returns the number of consecutive least significant zero
   // bits of x.
   func (x nat) trailingZeroBits() uint {
   	if len(x) == 0 {
   		return 0
   	}
   	var i uint
   	for x[i] == 0 {
   		i++
   	}
   	// x[i] != 0
   	return i*_W + trailingZeroBits(x[i])
   }
   

   この新しいメソッドは、多倍長整数 nat の末尾ゼロビット数を計算します。まず、配列の先頭（最下位ワード）から順にゼロのワードをスキップし、そのゼロワードの数 (i) を数えます。次に、最初の非ゼロワード x[i] の末尾ゼロビット数を、既存の trailingZeroBits(Word) 関数を使って計算し、これらを合計することで nat 全体の末尾ゼロビット数を求めます。これは、多倍長整数におけるビット操作の基本的なユーティリティとなります。

3. powersOfTwoDecompose 関数の削除: powersOfTwoDecompose は、数値 x を q * 2^k の形式に分解する関数でした。この機能は、新しく追加された nat.trailingZeroBits() と既存の nat.shr (右シフト) を組み合わせることで、より汎用的に実現できるため、削除されました。これにより、コードベースが簡素化され、特定の用途に特化した関数が減りました。

4. probablyPrime 関数での変更:

   --- a/src/pkg/math/big/nat.go
   +++ b/src/pkg/math/big/nat.go
   @@ -1343,8 +1334,9 @@ func (n nat) probablyPrime(reps int) bool {
    	}
    
    	nm1 := nat(nil).sub(n, natOne)
   -	// 1<<k * q = nm1;
   -	q, k := nm1.powersOfTwoDecompose()
   +	// determine q, k such that nm1 = q << k
   +	k := nm1.trailingZeroBits()
   +	q := nat(nil).shr(nm1, k)
    
    	nm3 := nat(nil).sub(nm1, natTwo)
    	rand := rand.New(rand.NewSource(int64(n[0])))\n@@ -1360,7 +1352,7 @@ NextRandom:\
    	\tif y.cmp(natOne) == 0 || y.cmp(nm1) == 0 {\
    	\t\tcontinue
    	\t}\
   -\t\tfor j := 1; j < k; j++ {\
   +\t\tfor j := uint(1); j < k; j++ {\
    	\t\ty = y.mul(y, y)\
    	\t\tquotient, y = quotient.div(y, y, n)\
    	\t\tif y.cmp(nm1) == 0 {\
   

   probablyPrime 関数は、ミラー・ラビン素数判定法の実装の一部として、n-1 を q * 2^k の形式に分解する必要があります。以前は powersOfTwoDecompose を使用していましたが、このコミットでは k を nm1.trailingZeroBits() で直接取得し、q を nm1 を k ビット右シフト (nat(nil).shr(nm1, k)) することで計算するように変更されました。これにより、コードがより直接的で理解しやすくなりました。また、ループ変数 j の型も uint に変更され、型の一貫性が保たれています。

src/pkg/math/big/nat_test.go の変更点

1. TestTrailingZeroBits の拡張:

   --- a/src/pkg/math/big/nat_test.go
   +++ b/src/pkg/math/big/nat_test.go
   @@ -613,14 +613,23 @@ func TestModW(t *testing.T) {
    }\
    \n func TestTrailingZeroBits(t *testing.T) {\
   -\tvar x Word\
   -\tx--\
   -\tfor i := 0; i < _W; i++ {\
   -\t\tif trailingZeroBits(x) != i {\
   -\t\t\tt.Errorf(\"Failed at step %d: x: %x got: %d\", i, x, trailingZeroBits(x))\
   +\tx := Word(1)\
   +\tfor i := uint(0); i <= _W; i++ {\
   +\t\tn := trailingZeroBits(x)\
   +\t\tif n != i%_W {\
   +\t\t\tt.Errorf(\"got trailingZeroBits(%#x) = %d; want %d\", x, n, i%_W)\
    \t\t}\
    \t\tx <<= 1
    \t}\
   +\
   +\ty := nat(nil).set(natOne)\
   +\tfor i := uint(0); i <= 3*_W; i++ {\
   +\t\tn := y.trailingZeroBits()\
   +\t\tif n != i {\
   +\t\t\tt.Errorf(\"got 0x%s.trailingZeroBits() = %d; want %d\", y.string(lowercaseDigits[0:16]), n, i)\
   +\t\t}\
   +\t\ty = y.shl(y, 1)\
   +\t}\
    }\
    \n var expNNTests = []struct {
   

   テストケースがより堅牢になりました。
   • Word 型の trailingZeroBits のテストでは、x を 1 から開始し、左シフトを繰り返すことで、各ビット位置での末尾ゼロビット数を正確に検証しています。i%_W を使用しているのは、_W ビットを超えるとパターンが繰り返されるためです。
   • 新しく追加された nat.trailingZeroBits() メソッドのテストでは、natOne (値が1の nat 型) から開始し、これを左シフト (y.shl(y, 1)) していくことで、nat 型の末尾ゼロビット数が期待通りに増加するかを検証しています。これにより、多倍長整数に対する trailingZeroBits の正確性が保証されます。

これらの変更は、math/big パッケージの内部実装をより効率的かつ保守しやすくするための重要なステップであり、特に binaryGCD のようなビット操作を多用するアルゴリズムの実装を容易にします。

関連リンク

• Go CL (Change List): https://golang.org/cl/6299064 これは、このコミットに対応するGoのコードレビューシステム（Gerrit）上の変更リストです。詳細な議論やレビューコメントがここに記録されています。

参考にした情報源リンク

• Donald Knuth, The Art of Computer Programming, Volume 4, Section 7.3.1: このコミットのコードコメントで言及されている「Knuth, volume 4, section 7.3.1」は、ドナルド・クヌースの著書「The Art of Computer Programming」の第4巻「Combinatorial Algorithms, Part 1」の7.3.1節「Bitwise Tricks & Techniques」を指しています。このセクションでは、ビット操作に関する様々なアルゴリズムやテクニックが解説されており、特に末尾ゼロビットを効率的に数えるDe Bruijnシーケンスに基づくアルゴリズムが詳細に説明されています。このアルゴリズムは、特定の定数とビットシフト、テーブルルックアップを組み合わせることで、CPUの特殊な命令（例: TZCNT や BSR）がない環境でも高速に末尾ゼロビット数を計算できるため、多くのプログラミング言語やライブラリで採用されています。

  • The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 (スタンフォード大学のDonald Knuthのウェブサイト)
  • Find first set - Wikipedia (De Bruijnシーケンスに基づくアルゴリズムの一般的な説明)

• Go math/big パッケージのドキュメント:

  • GoDoc: math/big package math/big パッケージの公式ドキュメントは、その機能、型、メソッドに関する詳細な情報を提供しています。nat 型や Word 型、そして様々な算術演算の動作を理解する上で不可欠な情報源です。

• Binary GCD algorithm - Wikipedia:

  • Binary GCD algorithm - Wikipedia binaryGCD アルゴリズムに関する詳細な説明は、このコミットの背景にある動機を理解する上で役立ちます。このアルゴリズムがなぜ trailingZeroBits を必要とするのか、そしてその効率性がどこから来るのかが解説されています。