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

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

このコミットは、Go言語の標準ライブラリmath/bigパッケージのInt型に、その内部表現であるビット列への直接的な（raw）アクセスを提供するBits()およびSetBits()メソッドを追加するものです。これにより、Int型が提供していない高度な機能を外部で効率的に実装することが可能になります。また、レシーバの命名規則に関する一貫性のない箇所が修正されています。

コミット

commit 71c19b610f1f5c0d61cc339d122eba730fc78c71
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Feb 1 11:43:40 2012 -0800

    mat/big: add raw access to Int bits

    This is a minimal API extension, it makes it possible
    to implement missing Int functionality externally w/o
    compromising efficiency. It is the hope that this will
    reduce the number of feature requests going directly
    into the big package.

    Also: Fixed some naming inconsistencies: The receiver
    is only called z when it is also the result.

    R=golang-dev, agl
    CC=golang-dev
    https://golang.org/cl/5607055

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

https://github.com/golang/go/commit/71c19b610f1f5c0d61cc339d122eba730fc78c71

元コミット内容

mat/big: add raw access to Int bits

This is a minimal API extension, it makes it possible
to implement missing Int functionality externally w/o
compromising efficiency. It is the hope that this will
reduce the number of feature requests going directly
into the big package.

Also: Fixed some naming inconsistencies: The receiver
is only called z when it is also the result.

R=golang-dev, agl
CC=golang-dev
https://golang.org/cl/5607055

変更の背景

この変更の主な背景は、math/bigパッケージのInt型が提供する機能の範囲と、ユーザーからの機能追加要求のバランスを取ることにあります。math/big.Intは任意精度整数を扱うための強力な型ですが、すべての可能な数学的演算やビット操作を網羅しているわけではありません。

コミットメッセージにあるように、「これは最小限のAPI拡張であり、効率を損なうことなく、不足しているIntの機能を外部で実装することを可能にする」という点が重要です。つまり、パッケージの内部実装に深く依存するような低レベルの操作を、パッケージ自体に直接追加するのではなく、ユーザーがIntの内部表現にアクセスできるようにすることで、外部で柔軟かつ効率的に実装できるようにする意図があります。これにより、math/bigパッケージへの直接的な機能追加要求の数を減らすことが期待されています。

また、Go言語のコーディング規約におけるレシーバの命名規則の一貫性を保つことも目的の一つです。特に、メソッドのレシーバがそのメソッドの戻り値でもある場合にのみzという名前を使用するという慣習に合わせるための修正が含まれています。

前提知識の解説

math/bigパッケージと任意精度整数

Go言語のmath/bigパッケージは、任意精度の数値を扱うための型を提供します。通常のGoの組み込み整数型（int, int64など）は、固定されたビット幅（例: 64ビット）で表現されるため、扱える数値の範囲に限界があります。これに対し、任意精度整数は、必要に応じてメモリを動的に割り当てることで、理論上はどんなに大きな整数でも表現できます。

math/big.Int型は、この任意精度整数を表現するための構造体です。内部的には、数値は通常、Word型のスライス（配列）として表現されます。Wordは、システムが効率的に扱えるワードサイズ（例: 32ビットまたは64ビット）の符号なし整数型です。数値の絶対値がこのWordスライスの要素として格納され、符号は別のフィールドで管理されます。

「Raw Access」の概念

「Raw Access」とは、データ構造の内部表現に直接アクセスすることを指します。通常、ライブラリやAPIは、内部の詳細を隠蔽し、抽象化されたインターフェース（メソッドなど）を通じてデータにアクセスすることを推奨します。これは、内部実装の変更が外部に影響を与えないようにするため、また、誤った使い方を防ぐためです。

しかし、特定の高度なユースケースでは、この抽象化が性能のボトルネックになったり、特定の機能の実装を不可能にしたりすることがあります。このような場合、ライブラリは「raw access」を許可するAPIを提供することがあります。これは通常、パフォーマンスが非常に重要であるか、またはライブラリが提供しない特定の低レベル操作が必要な場合に限られます。ただし、raw accessは内部実装に依存するため、将来のバージョンで互換性が失われるリスクを伴います。

Go言語のレシーバ命名規則

Go言語では、メソッドのレシーバ（メソッドが呼び出されるオブジェクト）の命名に関して一般的な慣習があります。

  • レシーバは通常、その型の最初の文字（例: *Int型ならi）を使用します。
  • ただし、メソッドがレシーバ自身を変更し、そのレシーバを結果として返す場合（例: Setメソッドなど）、レシーバ名をzとすることがよくあります。これは、数学的な文脈で結果を表す変数としてzが使われることに由来します。
  • レシーバが変更されず、単にその値を使用するだけのメソッド（例: String()やBytes()など）では、xやyといった一般的な変数名が使われることがあります。

このコミットでは、この慣習に沿って、Bytes(), BitLen(), ProbablyPrime(), Bit(), GobEncode()といったメソッドのレシーバ名がzからxに変更されています。これは、これらのメソッドがレシーバの値を変更せず、単にその値を読み取るだけであるためです。

技術的詳細

Bits()メソッドの追加

func (x *Int) Bits() []Word

  • 目的: Int型の絶対値を、リトルエンディアンのWordスライスとして返します。
  • 詳細:
    • レシーバはxと命名されています。これは、このメソッドがIntの値を変更しないためです。
    • 戻り値は[]Word型です。Wordはmath/bigパッケージ内で定義されている符号なし整数型で、通常はuintまたはuint64のエイリアスです。
    • 「リトルエンディアン」とは、数値の最下位ワード（最下位ビットを含むワード）がスライスの先頭（インデックス0）に格納されることを意味します。
    • 「The result and x share the same underlying array.」というコメントは非常に重要です。これは、返される[]Wordスライスが、Int型の内部で使用されている基盤となる配列を直接参照していることを意味します。したがって、このスライスを外部で変更すると、元のIntオブジェクトの値も変更されてしまう可能性があります。これは「unchecked but fast access」の典型的な例であり、非常に注意して使用する必要があります。
    • このメソッドは、x.abs（Int型の内部フィールドで絶対値をnat型、実質的には[]Wordとして保持している）を直接返しています。

SetBits()メソッドの追加

func (z *Int) SetBits(abs []Word) *Int

  • 目的: Int型の値を、与えられたWordスライスabsに基づいて設定し、Intオブジェクト自身を返します。
  • 詳細:
    • レシーバはzと命名されています。これは、このメソッドがレシーバであるIntオブジェクトの値を変更し、そのオブジェクトを戻り値として返すためです。
    • 引数absは、リトルエンディアンのWordスライスとして解釈されます。
    • 「The result and abs share the same underlying array.」というコメントは、Bits()と同様に、渡されたabsスライスがIntの内部配列として直接使用される可能性があることを示唆しています。これにより、コピーのオーバーヘッドを避けて効率的な設定が可能になりますが、absスライスを外部で変更すると、設定後のIntオブジェクトの値も意図せず変更されるリスクがあります。
    • z.abs = nat(abs).norm():
      • nat(abs): []Wordスライスをnat型にキャストしています。nat型はmath/bigパッケージ内で定義されている内部的な型で、任意精度整数の絶対値を表現するために使われます。
      • .norm(): nat型のnorm()メソッドは、スライスの末尾にあるゼロワードを削除し、数値の正規化を行います。例えば、[1, 2, 0, 0]のようなスライスが与えられた場合、[1, 2]に正規化されます。これにより、数値の表現が一意になり、不要なメモリ使用を避けることができます。
    • z.neg = false: SetBitsは絶対値のビット列を受け取るため、設定されるIntの符号は非負（0または正）に設定されます。負の値を表現したい場合は、別途SetSignなどのメソッドを使用する必要があります。

レシーバ命名規則の修正

以下のメソッドで、レシーバ名がzからxに変更されています。これは、これらのメソッドがレシーバの値を変更せず、単にその値を読み取るだけであるためです。

  • Bytes()
  • BitLen()
  • ProbablyPrime()
  • Bit()
  • GobEncode()

これらの変更は、Go言語の標準ライブラリにおける一貫したコーディングスタイルを維持するためのものです。

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

--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -65,6 +65,26 @@ func (z *Int) Set(x *Int) *Int {
 	return z
 }

+// Bits provides raw (unchecked but fast) access to x by returning its
+// absolute value as a little-endian Word slice. The result and x share
+// the same underlying array.
+// Bits is intended to support implementation of missing low-level Int
+// functionality outside this package; it should be avoided otherwise.
+func (x *Int) Bits() []Word {
+	return x.abs
+}
+
+// SetBits provides raw (unchecked but fast) access to z by setting its
+// value to abs, interpreted as a little-endian Word slice, and returning
+// z. The result and abs share the same underlying array.
+// SetBits is intended to support implementation of missing low-level Int
+// functionality outside this package; it should be avoided otherwise.
+func (z *Int) SetBits(abs []Word) *Int {
+	z.abs = nat(abs).norm()
+	z.neg = false
+	return z
+}
+
 // Abs sets z to |x| (the absolute value of x) and returns z.
 func (z *Int) Abs(x *Int) *Int {
 	z.Set(x)
@@ -528,18 +548,18 @@ func (z *Int) SetBytes(buf []byte) *Int {
 }

 // Bytes returns the absolute value of z as a big-endian byte slice.
-func (z *Int) Bytes() []byte {
-	buf := make([]byte, len(z.abs)*_S)
-	return buf[z.abs.bytes(buf):]
+func (x *Int) Bytes() []byte {
+	buf := make([]byte, len(x.abs)*_S)
+	return buf[x.abs.bytes(buf):]
 }

 // BitLen returns the length of the absolute value of z in bits.
 // The bit length of 0 is 0.
-func (z *Int) BitLen() int {
-	return z.abs.bitLen()
+func (x *Int) BitLen() int {
+	return x.abs.bitLen()
 }

-// Exp sets z = x**y mod m. If m is nil, z = x**y.\n+// Exp sets z = x**y mod m and returns z. If m is nil, z = x**y.
+// Exp sets z = x**y mod m and returns z. If m is nil, z = x**y.
 // See Knuth, volume 2, section 4.6.3.
 func (z *Int) Exp(x, y, m *Int) *Int {
 	if y.neg || len(y.abs) == 0 {
@@ -617,11 +637,11 @@ func GcdInt(d, x, y, a, b *Int) {
 	*d = *A
 }

-// ProbablyPrime performs n Miller-Rabin tests to check whether z is prime.\n-// If it returns true, z is prime with probability 1 - 1/4^n.\n-// If it returns false, z is not prime.\n-func ProbablyPrime(z *Int, n int) bool {\n-	return !z.neg && z.abs.probablyPrime(n)\n+// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.\n+// If it returns true, x is prime with probability 1 - 1/4^n.\n+// If it returns false, x is not prime.\n+func ProbablyPrime(x *Int, n int) bool {\n+	return !x.neg && x.abs.probablyPrime(n)\n }

 // Rand sets z to a pseudo-random number in [0, n) and returns z.
 @@ -671,18 +691,18 @@ func (z *Int) Rsh(x *Int, n uint) *Int {
 	return z
 }

-// Bit returns the value of the i\'th bit of z. That is, it\n-// returns (z>>i)&1. The bit index i must be >= 0.\n-func (z *Int) Bit(i int) uint {\n+// Bit returns the value of the i\'th bit of x. That is, it\n+// returns (x>>i)&1. The bit index i must be >= 0.\n+func (x *Int) Bit(i int) uint {\n 	if i < 0 {\n 		panic("negative bit index")\n 	}\n-\tif z.neg {\n-\t\tt := nat(nil).sub(z.abs, natOne)\n+\tif x.neg {\n+\t\tt := nat(nil).sub(x.abs, natOne)\n \t\treturn t.bit(uint(i)) ^ 1\n \t}\n \n-\treturn z.abs.bit(uint(i))\n+\treturn x.abs.bit(uint(i))\n }\n \n // SetBit sets z to x, with x\'s i\'th bit set to b (0 or 1).\n@@ -847,11 +867,11 @@ func (z *Int) Not(x *Int) *Int {
 const intGobVersion byte = 1

 // GobEncode implements the gob.GobEncoder interface.
-func (z *Int) GobEncode() ([]byte, error) {\n-\tbuf := make([]byte, 1+len(z.abs)*_S) // extra byte for version and sign bit\n-\ti := z.abs.bytes(buf) - 1            // i >= 0\n+func (x *Int) GobEncode() ([]byte, error) {\n+\tbuf := make([]byte, 1+len(x.abs)*_S) // extra byte for version and sign bit\n+\ti := x.abs.bytes(buf) - 1            // i >= 0\n \tb := intGobVersion << 1              // make space for sign bit\n-\tif z.neg {\n+\tif x.neg {\n \t\tb |= 1\n \t}\n \tbuf[i] = b

コアとなるコードの解説

Bits()とSetBits()の追加

  • Bits(): このメソッドは、Int型の内部表現であるx.abs（絶対値を表す[]Wordスライス）を直接返します。これにより、Intの内部データに直接アクセスし、低レベルのビット操作や、math/bigパッケージが提供しない特定のアルゴリズムを外部で実装することが可能になります。例えば、特定のビットパターンを検索したり、カスタムのビットシフト操作を行ったりする際に利用できます。ただし、返されたスライスを直接変更すると、元のIntオブジェクトの状態が意図せず変更される可能性があるため、細心の注意が必要です。

  • SetBits(): このメソッドは、与えられたWordスライスabsをInt型の新しい絶対値として設定します。nat(abs).norm()という呼び出しは、入力スライスをnat型（内部的な数値表現）に変換し、末尾のゼロワードを削除して正規化する役割を果たします。これにより、効率的かつ正確にIntの値を設定できます。このメソッドも、渡されたスライスが内部配列として共有される可能性があるため、使用には注意が必要です。

これらのメソッドは、math/bigパッケージの設計哲学である「効率を損なうことなく、不足しているIntの機能を外部で実装することを可能にする」という目標を達成するためのものです。

レシーバ命名規則の修正

Bytes(), BitLen(), ProbablyPrime(), Bit(), GobEncode()といったメソッドのレシーバ名がzからxに変更されました。

  • 変更前（例: func (z *Int) Bytes() []byte）: 以前は、これらのメソッドでもレシーバ名にzが使われていました。
  • 変更後（例: func (x *Int) Bytes() []byte）: 変更後は、レシーバ名がxになっています。

この変更は、Go言語の慣習に従い、メソッドがレシーバの値を変更しない場合にxを使用し、レシーバの値を変更してそれを戻り値として返す場合にzを使用するというルールを徹底するためのものです。これにより、コードの可読性と一貫性が向上します。

関連リンク

参考にした情報源リンク