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

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

このコミットは、Go言語のbignumパッケージ（当時の実験的な実装）における多倍長整数および有理数演算の機能拡張と改善を目的としています。具体的には、最大公約数（GCD）、べき乗、ビットカウント（population count）といった基本的な数値演算機能が追加され、有理数の正規化処理が導入されました。これにより、bignumパッケージの数学的演算能力が向上し、より堅牢な数値計算が可能になりました。

コミット

commit db27d309d1ff3b16c71995ea2ad55a5b17039042
Author: Robert Griesemer <gri@golang.org>
Date:   Fri Oct 31 16:58:56 2008 -0700

    - gcd, exponentiation, population count
    - more rational numbers stuff
    - more tests
    
    R=r
    OCL=18295
    CL=18295

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

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

元コミット内容

  • gcd, exponentiation, population count
  • more rational numbers stuff
  • more tests

変更の背景

このコミットが行われた2008年10月は、Go言語がまだ一般に公開される前の初期開発段階にありました。bignumパッケージは、多倍長整数（Natural、Integer）や有理数（Rational）といった、標準のプリミティブ型では扱えない非常に大きな数値や高精度な計算を可能にするための基盤を提供するものでした。

この時期のGo言語は、システムプログラミング言語としての基礎を固めつつあり、その中で数値計算の正確性と効率性は重要な要素でした。特に、暗号化、科学技術計算、金融アプリケーションなど、高精度な数値演算が求められる分野では、多倍長演算ライブラリが不可欠です。

このコミットの背景には、bignumパッケージの機能不足を解消し、より実用的な数値計算ライブラリへと進化させる意図があったと考えられます。GCD、べき乗、population countといった機能は、数論、アルゴリズム、データ構造の分野で頻繁に利用される基本的な演算であり、これらを効率的に実装することで、bignumパッケージの汎用性と性能が向上します。また、有理数の正規化は、有理数演算の正確性を保証し、冗長な表現を避けるために不可欠な処理です。

前提知識の解説

1. 多倍長整数 (BigNum)

通常のプログラミング言語の整数型（例: int32, int64）は、表現できる数値の範囲に限りがあります。多倍長整数（BigNumまたはArbitrary-Precision Arithmetic）は、この制限を取り払い、メモリが許す限り任意の大きさの整数を扱うことができるようにする技術です。通常、数値は配列やスライスに格納され、各要素が数値の一部（基数に応じた桁）を表します。加算、減算、乗算、除算などの演算は、これらの配列を操作する形で実装されます。

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

2つ以上の整数に共通する約数のうち、最も大きいものを最大公約数と呼びます。例えば、12と18の最大公約数は6です。GCDは、分数の約分（正規化）や、合同算術、暗号理論など、様々な数学的・計算機科学的応用で利用されます。

最も一般的なGCDの計算アルゴリズムはユークリッドの互除法です。これは、2つの整数 a と b (a > b) のGCDが、b と a を b で割った余り r のGCDに等しいという性質を利用します。このプロセスを余りが0になるまで繰り返すと、その時の b がGCDとなります。

3. べき乗 (Exponentiation)

ある数 x を n 回掛け合わせる演算を x の n 乗（x^n）と呼びます。例えば、2^3 = 2 * 2 * 2 = 8 です。多倍長整数におけるべき乗は、結果が非常に大きくなる可能性があるため、効率的なアルゴリズムが必要です。

**バイナリ法（二分法、Exponentiation by Squaring）**は、べき乗を効率的に計算するアルゴリズムです。これは、x^n を計算する際に、n のバイナリ表現を利用します。n のビットが1であれば現在の基底を結果に乗算し、常に基底を二乗していきます。これにより、乗算回数を大幅に削減できます。

例: x^10 (10はバイナリで 1010)

  1. n = 10 (1010_2)
  2. res = 1, base = x
  3. n の最下位ビットが0: base = x*x = x^2, n = 5 (0101_2)
  4. n の最下位ビットが1: res = res * base = 1 * x^2 = x^2, base = x^2 * x^2 = x^4, n = 2 (0010_2)
  5. n の最下位ビットが0: base = x^4 * x^4 = x^8, n = 1 (0001_2)
  6. n の最下位ビットが1: res = res * base = x^2 * x^8 = x^10, base = x^8 * x^8 = x^16, n = 0 (0000_2)
  7. n が0になったので終了。結果は x^10。

4. ビットカウント (Population Count / Hamming Weight)

ある数値のバイナリ表現において、セットされているビット（値が1のビット）の数を数える演算をビットカウント、またはポピュレーションカウント（Population Count）、ハミング重み（Hamming Weight）と呼びます。例えば、バイナリ 10110 (10進数で22) のビットカウントは3です。

ビットカウントは、データ圧縮、エラー訂正コード、暗号化、ハッシュ関数、グラフ理論など、様々な分野で利用されます。効率的なビットカウントアルゴリズムには、ビット操作を利用したループ処理や、ルックアップテーブル、CPUの専用命令（例: POPCNT命令）などがあります。

このコミットで使われている x &= x-1 のループは、ビットカウントの古典的なアルゴリズムの一つです。この操作は、数値 x の最下位のセットビットをクリアします。x が0になるまでこの操作を繰り返すことで、セットビットの数を数えることができます。

5. 有理数 (Rational Numbers)

有理数とは、2つの整数 a と b (b ≠ 0) を用いて a/b の分数として表せる数のことです。a を分子、b を分母と呼びます。有理数演算では、加算、減算、乗算、除算の際に、結果を有理数として正確に表現するために、分子と分母を適切に操作する必要があります。

6. 有理数の正規化 (Normalization of Rational Numbers)

有理数 a/b は、分子 a と分母 b をそれらの最大公約数で割ることで、最も簡単な形（既約分数）にすることができます。このプロセスを有理数の正規化と呼びます。例えば、6/12 は 1/2 に正規化されます。正規化は、有理数の比較を容易にし、計算結果の冗長性を排除するために重要です。

技術的詳細

このコミットは、bignumパッケージのNatural型（符号なし多倍長整数）とRational型（有理数）に新たなメソッドと機能を追加しています。

Natural型への追加機能

  1. Pop1(x Digit) uint:

    • 単一のDigit型（多倍長整数の内部表現における1桁、通常はuintやuint64）のビットカウントを計算します。
    • アルゴリズムは x &= x-1 を利用した古典的な方法です。これは、xの最下位ビットをクリアする操作をxが0になるまで繰り返し、その回数を数えることでビット数を求めます。

  2. (x *Natural) Pop() uint:

    • Natural型（多倍長整数）全体のビットカウントを計算します。
    • Natural型はDigitのスライスとして表現されるため、各Digitに対してPop1を呼び出し、その結果を合計することで全体のビットカウントを求めます。

  3. (x *Natural) Pow(n uint) *Natural:

    • Natural型のxをn乗するべき乗関数です。
    • **バイナリ法（Exponentiation by Squaring）**を実装しています。これは、nのバイナリ表現を利用して、乗算回数を対数的に削減する効率的なアルゴリズムです。
    • zを結果、xを基底として、nが0になるまでループします。
    • nの最下位ビットが1の場合（n&1 == 1）、zに現在のxを乗算します。
    • xをx.Mul(x)で二乗し、nをn/2で右シフトします。

  4. (x *Natural) Gcd(y *Natural) *Natural:

    • Natural型のxとyの最大公約数（GCD）を計算します。
    • ユークリッドの互除法を実装しています。
    • yがゼロでない間、xとyをそれぞれyとx.Mod(y)（xをyで割った余り）に置き換える操作を繰り返します。
    • yがゼロになった時点でのxがGCDとなります。

  5. export func Gcd(x, y T) T:

    • Tインターフェースを引数にとる汎用的なGCD関数です。
    • TインターフェースはIsZero() boolとMod(y T) boolメソッドを持つ型を要求します。これにより、Natural型だけでなく、将来的に他の数値型でもGCDを計算できるような拡張性を持たせています。
    • 実装は(x *Natural) Gcdと同様にユークリッドの互除法です。

Rational型（有理数）の改善

  1. NewRat関数の削除とRat関数の導入:

    • 以前のNewRat関数は単に分子と分母を受け取ってRational構造体を生成するだけでした。
    • 新しく導入されたfunc Rat(a, b *Integer) *Rationalは、Rational構造体を生成した後、Normalize()メソッドを呼び出して自動的に正規化を行います。これにより、有理数が常に既約分数として表現されるようになります。

  2. (x *Rational) Normalize() *Rational:

    • 有理数xを正規化するメソッドです。
    • 分子x.a.mantと分母x.b.mantの最大公約数fを計算します（Gcdメソッドを使用）。
    • 分子と分母をそれぞれfで割ることで、既約分数に変換します。

  3. 有理数演算メソッドの変更:

    • Add, Sub, Mul, Divといった有理数演算メソッドの戻り値が、以前のNewRatの代わりに新しいRat関数を使用するように変更されました。
    • これにより、これらの演算の結果として生成される有理数が、常に自動的に正規化されるようになりました。

その他の変更

  • Log1(x Digit) int関数に// BUG >>= broken for uint64というコメントが追加されています。これは、uint64型に対する右シフト演算子>>=にバグがある可能性を示唆しています。当時のGo言語のコンパイラやランタイムの未成熟さを示しています。
  • Integer型にQuo（商）とRem（剰余）のメソッドが追加されましたが、これらはpanic("UNIMPLEMENTED")となっており、まだ実装されていないことを示しています。

テストの追加

bignum_test.goには、新しく追加されたGcd、Pow、Pop関数のためのテストケースが追加されています。これにより、これらの新機能が正しく動作することを検証しています。

  • TestGcd(): 複数の数値ペアに対してGCDが正しく計算されることを確認。
  • TestPow(): 2^0から2^99までのべき乗が正しく計算されることを確認。特にBig.Nat(1).Shl(i)（1をiビット左シフト、つまり2^i）と比較することで、正確性を検証しています。
  • TestPop(): 様々な数値に対してビットカウントが正しく計算されることを確認。

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

usr/gri/bignum/bignum.go

// Pop1: 単一Digitのビットカウント
func Pop1(x Digit) uint {
	n := uint(0);
	for x != 0 {
		x &= x-1; // 最下位のセットビットをクリア
		n++;
	}
	return n;
}

// Pop: Natural型のビットカウント
func (x *Natural) Pop() uint {
	n := uint(0);
	for i := len(x) - 1; i >= 0; i-- {
		n += Pop1(x[i]); // 各Digitのビットカウントを合計
	}
	return n;
}

// Pow: Natural型のべき乗
func (x *Natural) Pow(n uint) *Natural {
	z := Nat(1); // 結果を1で初期化
	for n > 0 {
		// z * x^n == x^n0 (不変条件)
		if n&1 == 1 { // nの最下位ビットが1の場合
			z = z.Mul(x); // 結果に現在のxを乗算
		}
		x, n = x.Mul(x), n/2; // xを二乗し、nを右シフト
	}
	return z;
}

// Gcd: Natural型の最大公約数 (ユークリッドの互除法)
func (x *Natural) Gcd(y *Natural) *Natural {
	for !y.IsZero() {
		x, y = y, x.Mod(y); // x, y = y, x % y
	}
	return x;
}

// 汎用Gcd関数 (インターフェースTを使用)
export type T interface {
	IsZero() bool;
	Mod(y T) bool; // ここはMod(y T) T の間違いか、あるいはModがboolを返す特殊なケースか
}

export func Gcd(x, y T) T {
	for !y.IsZero() {
		x, y = y, x.Mod(y);
	}
	return x;
}

// Rational型の正規化
func (x *Rational) Normalize() *Rational {
	f := x.a.mant.Gcd(x.b.mant); // 分子と分母のGCDを計算
	x.a.mant = x.a.mant.Div(f);  // 分子をGCDで割る
	x.b.mant = x.b.mant.Div(f);  // 分母をGCDで割る
	return x;
}

// Rat: Rational型のコンストラクタ (正規化を含む)
func Rat(a, b *Integer) *Rational {
	return (&Rational{a, b}).Normalize(); // 生成後に正規化
}

// Rational演算メソッドの変更 (Rat関数を使用)
func (x *Rational) Add(y *Rational) *Rational {
	return Rat((x.a.Mul(y.b)).Add(x.b.Mul(y.a)), x.b.Mul(y.b));
}
// Sub, Mul, Div も同様に Rat を使用するように変更

usr/gri/bignum/bignum_test.go

// TestGcd: Gcd関数のテスト
func TestGcd() {
	test_msg = "TestGcdA";
	f := Big.Nat(99991);
	// 期待値: Big.MulRange(1, 20).Mul(f) は 1から20までの積にfを掛けたもの
	// 実際の計算: b.Mul(f).Gcd(c.Mul(f))
	// ここで b と c はテストスイート内で定義されたBig.Natオブジェクト
	TEST_EQ(0, b.Mul(f).Gcd(c.Mul(f)), Big.MulRange(1, 20).Mul(f));
}

// TestPow: Pow関数のテスト
func TestPow() {
	test_msg = "TestPowA";
	TEST_EQ(0, Big.Nat(2).Pow(0), Big.Nat(1)); // 2^0 = 1

	test_msg = "TestPowB";
	for i := uint(0); i < 100; i++ {
		// 2^i が 1をiビット左シフトしたものと等しいことを確認
		TEST_EQ(i, Big.Nat(2).Pow(i), Big.Nat(1).Shl(i));
	}
}

// TestPop: Pop関数のテスト
func TestPop() {
	test_msg = "TestPopA";
	TEST(0, Big.Nat(0).Pop() == 0); // 0のビットカウントは0
	TEST(1, Big.Nat(1).Pop() == 1); // 1のビットカウントは1
	TEST(2, Big.Nat(10).Pop() == 2); // 10 (1010_2) のビットカウントは2
	TEST(3, Big.Nat(30).Pop() == 4); // 30 (11110_2) のビットカウントは4
	TEST(4, Big.Nat(0x1248f).Shl(33).Pop() == 8); // 複雑な数値のビットカウント

	test_msg = "TestPopB";
	for i := uint(0); i < 100; i++ {
		// (2^i - 1) のビットカウントが i と等しいことを確認 (例: 2^3-1 = 7 (111_2) -> 3ビット)
		TEST(i, Big.Nat(1).Shl(i).Sub(Big.Nat(1)).Pop() == i);
	}
}

// main関数に新しいテストを追加
func main() {
	TestConv();
	TestShift();
	TestMul();
	TestDiv();
	TestMod();
	TestGcd(); // 追加
	TestPow(); // 追加
	TestPop(); // 追加
	print("PASSED\\n");
}

コアとなるコードの解説

このコミットの核となる変更は、bignumパッケージにおける数値演算の基礎的なビルディングブロックの追加と、有理数演算の堅牢化です。

Pop1 と Pop (ビットカウント)

Pop1関数は、単一のDigit（Goのuint型に相当）内のセットビット数を効率的に計算します。x &= x-1というイディオムは、数値の最下位のセットビットをクリアする効果があります。例えば、x = 10 (1010_2)の場合：

  1. x = 1010_2, x-1 = 1001_2 -> x &= x-1 は 1010_2 & 1001_2 = 1000_2 (nは1)
  2. x = 1000_2, x-1 = 0111_2 -> x &= x-1 は 1000_2 & 0111_2 = 0000_2 (nは2) xが0になったのでループ終了。結果は2。これは10のバイナリ表現1010_2のセットビット数と一致します。 Natural型のPopメソッドは、このPop1をNatural型を構成する各Digitに対して適用し、その合計を返すことで、多倍長整数全体のビットカウントを実現しています。

Pow (べき乗)

Powメソッドは、多倍長整数のべき乗を計算するために、**バイナリ法（Exponentiation by Squaring）**を採用しています。このアルゴリズムは、nのバイナリ表現を右から左へ（または左から右へ）走査し、nのビットが1であれば結果に現在の基底を乗算し、常に基底を二乗していくことで、乗算回数をO(log n)に削減します。 例えば、x^10を計算する場合、10のバイナリは1010です。

  • n=10 (1010_2): z=1, x=x
  • nの最下位ビットは0。x = x*x = x^2。n = 5 (0101_2)。
  • nの最下位ビットは1。z = z*x = 1*x^2 = x^2。x = x*x = x^4。n = 2 (0010_2)。
  • nの最下位ビットは0。x = x*x = x^8。n = 1 (0001_2)。
  • nの最下位ビットは1。z = z*x = x^2*x^8 = x^10。x = x*x = x^16。n = 0 (0000_2)。 nが0になったので終了。結果はx^10。 この方法は、単純にxをn回掛けるよりもはるかに効率的です。

Gcd (最大公約数)

Natural型と汎用インターフェースTの両方で提供されるGcd関数は、ユークリッドの互除法を実装しています。これは、2つの数値aとbのGCDが、bとaをbで割った余りのGCDに等しいという原理に基づいています。 for !y.IsZero() { x, y = y, x.Mod(y); } のループは、この原理を直接コードに落とし込んだものです。x.Mod(y)はxをyで割った余りを計算します。yが0になったとき、その時点のxが元の2つの数値のGCDとなります。このアルゴリズムは、非常に効率的で、多倍長整数に対しても適用可能です。

Rational型の正規化と演算

有理数Rationalの扱いが大幅に改善されました。以前はNewRat関数が単に分子と分母を受け取るだけでしたが、新しいRat関数は、Rationalオブジェクトを生成した直後にNormalize()メソッドを呼び出すようになりました。 Normalize()メソッドは、分子と分母のGCDを計算し、そのGCDで両方を割ることで、有理数を常に既約分数（最も簡単な形）に変換します。これにより、1/2と2/4のような同じ値を異なる表現で持つことがなくなり、有理数の比較や演算結果の一貫性が保証されます。 さらに、Add, Sub, Mul, Divといった有理数演算メソッドも、結果を生成する際にRat関数を使用するように変更されました。これにより、有理数演算のすべての結果が自動的に正規化されるようになり、ライブラリの使いやすさと正確性が向上しています。

これらの変更は、bignumパッケージがより堅牢で、数学的に正確な多倍長数値演算ライブラリとして機能するための重要なステップでした。

関連リンク

参考にした情報源リンク