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

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

コミット

  • コミットハッシュ: 1db31f8933ca3d3b2ce6d8decd01fe8acfcdecb6
  • 作成者: Robert Griesemer gri@golang.org
  • 日付: 2011年10月18日 09:45:38 -0700
  • コミットメッセージ: "big: more explicit documentation for div/mod/quo/rem"
  • 修正対象: Fixes #2380
  • レビュー: R=rsc, rogpeppe
  • 対象ファイル: src/pkg/big/int.go (8行中4行追加、4行削除)

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

https://github.com/golang/go/commit/1db31f8933ca3d3b2ce6d8decd01fe8acfcdecb6

元コミット内容

このコミットは、Go言語の math/big パッケージにおける整数の除算（division）、剰余（modulo）、商（quotient）、および余り（remainder）操作に関するドキュメントを、より明確で詳細なものに改善したものです。

変更内容：

  • src/pkg/big/int.go ファイルの8行を変更
  • 4行を追加、4行を削除
  • 除算関連メソッドの説明を詳細化
  • Issue #2380 の修正

変更の背景

Issue #2380の問題

Issue #2380は、Go言語の big.Int.Div メソッドが負の分子（numerator）に対して誤った結果を返すという問題でした。具体的には、期待される結果が0であるべきケースで-1を返すという動作が報告されました。

ドキュメント改善の必要性

この問題の根本原因は、除算関連メソッドの違いについてのドキュメントが不十分であったことにありました。特に：

  1. Div と Quo の違いが明確でない
  2. Euclidean division（ユークリッド除算）とT-division（截断除算）の違いの説明不足
  3. 負の数値に対する動作の違いについての説明不足

Robert Griesemer氏の貢献

Robert Griesemer氏は、Go言語の創設者の一人であり、以下の経歴を持つ著名な計算機科学者です：

  • ETH Zürichで博士号を取得（指導教員：Hanspeter Mössenböck、Niklaus Wirth）
  • Google V8 JavaScript エンジンの開発
  • Sawzall言語の設計
  • Java HotSpot仮想マシンの開発
  • Go言語の設計と実装（Rob Pike、Ken Thompsonと共同）

前提知識の解説

大きな整数（Big Integer）の必要性

通常のプログラミング言語では、整数は固定長（例：32ビット、64ビット）で表現されます。しかし、暗号学、数学的計算、科学計算などでは、これらの制限を超える任意精度の整数が必要になります。

除算の種類

1. T-division（截断除算）

  • 結果を0に向けて截断する
  • Goの標準的な除算と同じ動作
  • x/y の結果を0に向けて截断

2. Euclidean division（ユークリッド除算）

  • 剰余が常に非負になるように商を調整
  • 数学的により厳密な定義
  • 0 <= r < |y| の条件を満たす

Go言語における除算メソッド

Go言語の math/big パッケージでは、以下のメソッドが提供されています：

  • Quo: 商を求める（T-division）
  • Rem: 余りを求める（T-division）
  • QuoRem: 商と余りを同時に求める（T-division）
  • Div: 商を求める（Euclidean division）
  • Mod: 剰余を求める（Euclidean division）
  • DivMod: 商と剰余を同時に求める（Euclidean division）

技術的詳細

除算アルゴリズムの数学的基盤

除算操作は、以下の等式を満たす必要があります：

u = quo × v + rem

T-division（截断除算）の定義

  • quo = trunc(u/v)（0に向けて截断）
  • rem = u - quo × v
  • |rem| < |v|
  • rem の符号は u と同じ

Euclidean division（ユークリッド除算）の定義

  • quo = floor(u/v)（負の無限大に向けて截断）
  • rem = u - quo × v
  • 0 <= rem < |v|
  • rem は常に非負

負の数値に対する動作の違い

例：-7 ÷ 3 の場合

T-division（QuoRem）:

  • quo = -2（-2.333...を0に向けて截断）
  • rem = -1（-7 - (-2) × 3 = -1）

Euclidean division（DivMod）:

  • quo = -3（-2.333...を負の無限大に向けて截断）
  • rem = 2（-7 - (-3) × 3 = 2）

パフォーマンス考慮事項

大きな整数の除算は計算コストが高い操作です。QuoRem や DivMod メソッドは、商と剰余を同時に計算するため、個別に計算するよりも効率的です。

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

このコミットでは、src/pkg/big/int.go ファイルの以下の部分が変更されました：

  1. Div メソッドのドキュメント改善

    • Euclidean division の説明を詳細化
    • T-division との違いを明確化

  2. Mod メソッドのドキュメント改善

    • Euclidean modulus の説明を詳細化
    • 結果の範囲（0 <= m < |y|）を明記

  3. Quo メソッドのドキュメント改善

    • T-division の説明を詳細化
    • 截断動作の説明を追加

  4. Rem メソッドのドキュメント改善

    • T-division remainder の説明を詳細化
    • 符号の取り扱いを明確化

コアとなるコードの解説

ドキュメント改善の具体的内容

このコミットは主にドキュメントの改善であり、実際のコードロジックの変更はありません。しかし、以下の点で重要な改善がなされました：

1. 明確な用語の使用

  • "division" と "quotient" の違いを明確化
  • "modulus" と "remainder" の違いを明確化

2. 数学的定義の追加

  • Raymond T. Boute の論文「The Euclidean definition of the functions div and mod」への参照
  • 具体的な数式による説明

3. 動作の比較

  • Go言語の標準的な除算動作との比較
  • 各メソッドの使い分けの指針

実装上の配慮

// Div sets z to the quotient x/y for y != 0 and returns z.
// Div implements Euclidean division (unlike Go); see DivMod for more details.
func (z *Int) Div(z, x, y *Int) *Int

// Quo sets z to the quotient x/y for y != 0 and returns z.
// Quo implements truncated division (like Go); see QuoRem for more details.
func (z *Int) Quo(z, x, y *Int) *Int

この改善により、開発者は用途に応じて適切なメソッドを選択できるようになりました。

関連リンク

参考にした情報源リンク