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

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

このコミットは、Go言語の初期段階における任意精度演算ライブラリ（bignumパッケージ）に、除算（div）と剰余（mod）の機能を追加し、既存のコードベースの整理とテストの拡充を行ったものです。特に、KnuthのアルゴリズムDに基づいた多倍長整数除算の実装が主要な変更点となっています。

コミット

commit afad827255748a9046c35d8ffa8267d7b4f3bdf3
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Oct 30 23:37:34 2008 -0700

    - div and mod (arbitrary precision)
    - more tests
    - some global renames
    
    R=r
    OCL=18219
    CL=18219

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

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

元コミット内容

  • 任意精度での除算と剰余演算の追加
  • テストケースの拡充
  • グローバルな変数名の一部変更

変更の背景

このコミットは、Go言語の初期開発段階において、bignumパッケージに基本的な算術演算機能を追加する一環として行われました。多倍長整数演算において、加算、減算、乗算に加えて、除算と剰余は不可欠な操作です。これらの機能が欠けていると、より複雑な数値計算や暗号化などの用途でbignumパッケージを使用することができません。

また、既存のコードベースの可読性と保守性を向上させるために、型名や変数名の整理（WordからDigitへの変更など）が行われました。これにより、コードの意図がより明確になり、将来的な拡張やデバッグが容易になります。

前提知識の解説

任意精度演算（多倍長整数演算）

任意精度演算とは、コンピュータの固定されたワードサイズ（例: 32ビットや64ビット）に制限されず、必要に応じて任意の桁数の整数を扱うことができる演算のことです。通常の整数型では表現できない非常に大きな数や、小数点以下の精度を厳密に管理する必要がある場合に用いられます。

任意精度演算は、通常、整数の各桁を配列の要素として格納し、筆算の要領で加算、減算、乗算、除算などの演算を行います。このコミットでは、Digit型（uint64）の配列として多倍長整数を表現しています。

多倍長整数除算アルゴリズム（KnuthのアルゴリズムD）

多倍長整数除算は、固定長の整数除算よりも複雑なアルゴリズムを必要とします。このコミットで実装されているDivMod関数は、ドナルド・クヌース（Donald Knuth）の著書「The Art of Computer Programming, Volume 2: Seminumerical Algorithms」で詳細に解説されている「アルゴリズムD」（Algorithm D）に基づいています。

アルゴリズムDは、筆算の除算を多倍長整数に適用したもので、以下の主要なステップを含みます。

  1. 正規化（Normalization）: 除数（y）の最上位桁が特定の範囲内にあるように、被除数（x）と除数を同じ係数でスケーリングします。これにより、試行商（trial digit）の推定精度が向上し、アルゴリズムの収束が速くなります。
  2. 試行商の推定（Trial Digit Estimation）: 被除数と除数の最上位の数桁を用いて、現在の部分的な被除数に対する商の桁を推定します。この推定は、正確な商の桁に近い値を得るために重要です。
  3. 部分的な減算（Partial Subtraction）: 推定された試行商と除数を乗算し、その結果を現在の部分的な被除数から減算します。
  4. 試行商の修正（Correction of Trial Digit）: 減算の結果が負になった場合、試行商が大きすぎたことを意味するため、試行商を減らし、除数を部分的な被除数に加算して修正します。
  5. 繰り返し: 上記のステップを、被除数のすべての桁が処理されるまで繰り返します。

このアルゴリズムは、効率的かつ正確に多倍長整数除算を行うための標準的な方法として広く知られています。

技術的詳細

bignum.goの変更点

  • 型エイリアスの変更:
    • type Word uint64; が type Digit uint64; に変更されました。これにより、多倍長整数の各桁を表現する型がより直感的な名前に変わりました。
    • type Word3 uint32; が type Digit3 uint32; に変更されました。これは、除算アルゴリズム内で一時的に使用される、より小さな桁を表現するための型です。
    • type Natural []Word; が type Natural []Digit; に変更されました。
  • 定数の変更:
    • LogW, LogH, H, LogB, L, B, M といった基数に関する定数の定義が変更されました。特に、DivMod関数がDigitが最大のuintサイズを使用している場合に利用できないため、除算前に基数を分割し、後でマージするロジックが導入されました。これに伴い、L3, B3, M3に加えて、L2, B2, M2が追加されました。
  • ヘルパー関数の変更:
    • IsSmall, Split, Dump, NewNat（Natにリネーム）、Normalize3などの関数が、新しい型エイリアス（Digit, Digit3）を使用するように更新されました。
    • Dump3関数が追加され、Digit3配列のダンプが可能になりました。
  • 算術演算関数の変更:
    • Add, Sub, MulAdd1, Mul1, Shl1, Shr1などの既存の算術演算関数も、WordからDigitへの型変更に合わせてシグネチャが更新されました。
  • 除算・剰余関連の新規関数:
    • SplitBase(x *Natural) *[]Digit3: Natural型の多倍長整数を、Digit3型の配列に分割します。これは、DivMod関数がDigitが最大のuintサイズを使用している場合に、より小さな基数で除算を行うために必要です。
    • MergeBase(x *[]Digit3) *Natural: Digit3型の配列を、元のNatural型にマージします。
    • Split3(x Digit) (Digit, Digit3): DigitをL3ビットで分割します。
    • Product(x *[]Digit3, y Digit): Digit3配列xの各要素にyを乗算します。正規化ステップで使用されます。
    • Quotient(x *[]Digit3, y Digit): Digit3配列xの各要素をyで除算します。正規化解除ステップで使用されます。
    • DivMod(x, y *[]Digit3) (*[]Digit3, *[]Digit3): このコミットの核心となる関数です。 KnuthのアルゴリズムDに基づき、Digit3型の配列で表現された被除数xと除数yに対して、商と剰余を計算します。
      • 単一桁での除算（m == 1）と、一般的な多桁での除算（m > 1）の両方を扱います。
      • 正規化（Product(x, f)とProduct(y, f)）と正規化解除（Quotient(x[0 : m], f)）のステップが含まれています。
      • 試行商の推定と、その後の部分的な減算、そして必要に応じた試行商の修正ロジックが実装されています。
    • Div(y *Natural) *Natural: Natural型の除算をDivMod関数を呼び出すことで実装します。
    • Mod(y *Natural) *Natural: Natural型の剰余をDivMod関数を呼び出すことで実装します。
  • その他の変更:
    • Cmp, Log1, DivMod1, String, MulRange, Fact, HexValue, NatFromString, Int, Integer.String, IntFromStringなどの関数も、WordからDigitへの型変更に合わせてシグネチャが更新されました。

bignum_test.goの変更点

  • インポートエイリアスの変更:
    • import Bignum "bignum" が import Big "bignum" に変更されました。
  • テストヘルパー関数の変更:
    • TEST関数の引数nの型がintからuintに変更されました。
    • TEST_EQ(n uint, x, y *Big.Natural)関数が追加されました。これは、2つのNatural型の値が等しいことを比較し、等しくない場合に詳細なエラーメッセージを出力するヘルパー関数です。これにより、テストコードの可読性とデバッグの容易性が向上しました。
  • 既存テストの更新:
    • TestConvとTestShift関数が、新しいBig.Nat関数とTEST_EQヘルパー関数を使用するように更新されました。
  • 新規テスト関数の追加:
    • TestMul(): 乗算機能のテストケースが追加されました。特に、シフト演算と組み合わせた乗算のプロパティを検証しています。
    • TestDiv(): 除算機能のテストケースが追加されました。 1による除算、大きな数による除算、シフト演算と組み合わせた除算など、様々なシナリオを検証しています。
    • TestMod(): 剰余機能のテストケースが追加されました。 加算と組み合わせた剰余のプロパティを検証しています。
  • main関数の更新:
    • main関数にTestMul(), TestDiv(), TestMod()の呼び出しが追加され、新しいテストが実行されるようになりました。

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

このコミットのコアとなる変更は、bignum.goファイルにおけるDivMod関数の実装と、それに伴う関連ヘルパー関数の追加および既存関数の修正です。

特に、DivMod関数は、多倍長整数除算の複雑なロジックをカプセル化しており、KnuthのアルゴリズムDをGo言語で実装したものです。

// DivMod needs multi-precision division which is not available if Digit
// is already using the largest uint size. Split base before division,
// and merge again after. Each Digit is split into 3 Digit3's.

func SplitBase(x *Natural) *[]Digit3 {
	// TODO Use Log() for better result - don't need Normalize3 at the end!
	n := len(x);
	z := new([]Digit3, n*3 + 1);  // add space for extra digit (used by DivMod)
	for i, j := 0, 0; i < n; i, j = i+1, j+3 {
		t := x[i];
		z[j+0] = Digit3(t >> (L3*0) & M3);
		z[j+1] = Digit3(t >> (L3*1) & M3);
		z[j+2] = Digit3(t >> (L3*2) & M3);
	}
	return Normalize3(z);
}

func MergeBase(x *[]Digit3) *Natural {
	i := len(x);
	j := (i+2)/3;
	z := new(Natural, j);

	switch i%3 {
	case 1: z[j-1] = Digit(x[i-1]); i--; j--;
	case 2: z[j-1] = Digit(x[i-1])<<L3 | Digit(x[i-2]); i -= 2; j--;
	case 0:
	}
	
	for i >= 3 {
		z[j-1] = ((Digit(x[i-1])<<L3) | Digit(x[i-2]))<<L3 | Digit(x[i-3]);
		i -= 3;
		j--;
	}
	assert(j == 0);

	return Normalize(z);
}

func Split3(x Digit) (Digit, Digit3) {
	return uint64(int64(x)>>L3), Digit3(x&M3)
}

func Product(x *[]Digit3, y Digit) {
	n := len(x);
	c := Digit(0);
	for i := 0; i < n; i++ { c, x[i] = Split3(Digit(x[i])*y + c) }
	assert(c == 0);
}

func Quotient(x *[]Digit3, y Digit) {
	n := len(x);
	c := Digit(0);
	for i := n-1; i >= 0; i-- {
		t := c*B3 + Digit(x[i]);
		c, x[i] = t%y, Digit3(t/y);
	}
	assert(c == 0);
}

// Division and modulo computation - destroys x and y. Based on the
// algorithms described in:
//
// 1) D. Knuth, "The Art of Computer Programming. Volume 2. Seminumerical
//    Algorithms." Addison-Wesley, Reading, 1969.
//
// 2) P. Brinch Hansen, Multiple-length division revisited: A tour of the
//    minefield. "Software - Practice and Experience 24", (June 1994),
//    579-601. John Wiley & Sons, Ltd.
//
// Specifically, the inplace computation of quotient and remainder
// is described in 1), while 2) provides the background for a more
// accurate initial guess of the trial digit.

func DivMod(x, y *[]Digit3) (*[]Digit3, *[]Digit3) {
	const b = B3;
	
	n := len(x);
	m := len(y);
	assert(m > 0);  // division by zero
	assert(n+1 <= cap(x));  // space for one extra digit (should it be == ?)
	x = x[0 : n + 1];
	
	if m == 1 {
		// division by single digit
		d := Digit(y[0]);
		c := Digit(0);
		for i := n; i > 0; i-- {
			t := c*b + Digit(x[i-1]);
			c, x[i] = t%d, Digit3(t/d);
		}
		x[0] = Digit3(c);

	} else if m > n {
		// quotient = 0, remainder = x
		// TODO in this case we shouldn't even split base - FIX THIS
		m = n;
		
	} else {
		// general case
		assert(2 <= m && m <= n);
		assert(x[n] == 0);
		
		// normalize x and y
		f := b/(Digit(y[m-1]) + 1);
		Product(x, f);
		Product(y, f);
		assert(b/2 <= y[m-1] && y[m-1] < b);  // incorrect scaling
		
		d2 := Digit(y[m-1])*b + Digit(y[m-2]);
		for i := n-m; i >= 0; i-- {
			k := i+m;
			
			// compute trial digit
			r3 := (Digit(x[k])*b + Digit(x[k-1]))*b + Digit(x[k-2]);
			q := r3/d2;
			if q >= b { q = b-1 }
			
			// subtract y*q
			c := Digit(0);
			for j := 0; j < m; j++ {
				c, x[i+j] = Split3(c + Digit(x[i+j]) - Digit(y[j])*q);
			}
			
			// correct if trial digit was too large
			if c + Digit(x[k]) != 0 {
				// add y
				c := Digit(0);
				for j := 0; j < m; j++ {
					c, x[i+j] = Split3(c + Digit(x[i+j]) + Digit(y[j]));
				}
				// correct trial digit
				q--;
			}
			
			x[k] = Digit3(q);
		}
		
		// undo normalization for remainder
		Quotient(x[0 : m], f);
	}

	return x[m : n+1], x[0 : m];
}

func (x *Natural) Div(y *Natural) *Natural {
	q, r := DivMod(SplitBase(x), SplitBase(y));
	return MergeBase(q);
}

func (x *Natural) Mod(y *Natural) *Natural {
	q, r := DivMod(SplitBase(x), SplitBase(y));
	return MergeBase(r);
}

コアとなるコードの解説

DivMod関数は、多倍長整数除算の主要なロジックを実装しています。

  1. 基数の分割とマージ:

    • DivMod関数は、Natural型（Digitの配列）ではなく、Digit3型の配列を引数として受け取ります。これは、Digitがuint64であり、これ以上分割できない場合に、より小さな基数（B3）で除算を行うためです。
    • SplitBase関数は、Natural型の多倍長整数をDigit3型の配列に変換します。各Digitは3つのDigit3に分割されます。
    • MergeBase関数は、Digit3型の配列をNatural型に変換し直します。
    • DivとMod関数は、これらのSplitBaseとMergeBaseを呼び出すことで、DivModをラップしています。

  2. 正規化:

    • DivModの汎用ケース（m > 1）では、まず被除数xと除数yを正規化します。これは、除数yの最上位桁がB3/2以上になるように、両方を同じ係数fで乗算することによって行われます。この正規化により、試行商の推定がより正確になります。
    • Product関数は、Digit3配列の各要素にfを乗算し、桁上がりを処理します。

  3. 試行商の推定と減算:

    • ループ内で、現在の部分的な被除数（x[k], x[k-1], x[k-2]）と除数の最上位2桁（y[m-1], y[m-2]）を用いて、試行商qを推定します。
    • 推定されたqと除数yを乗算し、その結果を部分的な被除数から減算します。この減算は、Split3関数を使用して桁上がりを処理しながら行われます。

  4. 試行商の修正:

    • 減算の結果、最上位桁に負の値（または桁借り）が発生した場合、推定された試行商qが大きすぎたことを意味します。この場合、qを1減らし、除数yを部分的な被除数に加算して修正します。

  5. 正規化解除:

    • すべての桁が処理された後、剰余に対して正規化を解除します。これは、正規化ステップで乗算した係数fで剰余を除算することによって行われます。
    • Quotient関数は、Digit3配列の各要素をfで除算し、桁下がりを処理します。

この一連の処理により、多倍長整数の正確な除算と剰余が計算されます。テストコードでは、これらの新しい機能が正しく動作することを検証するための包括的なテストケースが追加されています。

関連リンク

  • Go言語のmath/bigパッケージ - このコミットで実装されたbignumパッケージは、Go言語の標準ライブラリであるmath/bigパッケージの基礎となっています。

参考にした情報源リンク

  • D. Knuth, "The Art of Computer Programming. Volume 2. Seminumerical Algorithms." Addison-Wesley, Reading, 1969.
    • 特に、多倍長整数除算のアルゴリズムDに関する章が参考になっています。
  • P. Brinch Hansen, Multiple-length division revisited: A tour of the minefield. "Software - Practice and Experience 24", (June 1994), 579-601. John Wiley & Sons, Ltd.
    • 試行商のより正確な初期推定に関する背景情報を提供しています。