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

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

このコミットは、Go言語のmathパッケージにおけるLog2関数の実装を改善し、特に2のべき乗に対する計算結果の精度を保証することを目的としています。具体的には、浮動小数点数の指数部を分離して処理することで、Log2(2^n)が正確にnを返すように修正されています。

コミット

commit a3677b5f223db6ccadf26f81a751c4f8c8c0eaf9
Author: Russ Cox <rsc@golang.org>
Date:   Thu Dec 20 12:23:27 2012 -0500

    math: handle exponent separately in Log2
    
    This guarantees that powers of two return exact answers.
    
    We could do a multiprecision approximation for the
    rest of the answer too, but this seems like it should be
    good enough.
    
    Fixes #4567.
    
    R=golang-dev, iant, remyoudompheng
    CC=golang-dev
    https://golang.org/cl/6943074

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

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

元コミット内容

このコミットは、Log2関数が2のべき乗に対して正確な結果を返すように修正します。

コミットメッセージの要約:

  • Log2関数で指数部を個別に処理する。
  • これにより、2のべき乗が正確な答えを返すことが保証される。
  • 残りの部分についても多倍長精度近似を行うことは可能だが、現状で十分と判断。
  • Issue #4567 を修正。

変更の背景

この変更の背景には、浮動小数点演算における精度の問題、特にLog2関数が2のべき乗（例: 2, 4, 8, 16...）に対して期待される整数値を正確に返さないという問題がありました。浮動小数点数はその性質上、多くの実数を正確に表現できず、近似値として扱われます。しかし、2のべき乗の対数（底2）は常に整数になるため、これらの値については正確な結果が強く求められます。

Issue #4567（"math: Log2(2**N) should be N"）では、Log2(2**N)がNを返さないという具体的な問題が報告されていました。例えば、Log2(1)が0ではなく4.9406564584124654e-324のような非常に小さい非ゼロ値を返したり、Log2(2)が1ではなく0.9999999999999999のような値になったりすることが指摘されていました。これは、Log2(x)がLog(x) * (1 / Ln2)として計算されていたため、Log(x)と1/Ln2の浮動小数点近似誤差が累積して発生していました。

この問題は、特に数値計算や科学技術計算において、2のべき乗が頻繁に登場し、その対数が正確であることが前提とされる場合に、予期せぬ誤差やバグを引き起こす可能性がありました。そのため、このコミットは、Log2関数が2のべき乗に対して厳密な結果を返すようにすることで、関数の信頼性と予測可能性を高めることを目的としています。

前提知識の解説

浮動小数点数 (Floating-Point Numbers)

コンピュータにおける浮動小数点数は、実数を近似的に表現するための形式です。IEEE 754規格が広く用いられており、Go言語のfloat64型もこれに準拠しています。浮動小数点数は通常、符号部、指数部、仮数部（または分数部）の3つの要素で構成されます。

  • 符号部 (Sign): 数の正負を表します。
  • 指数部 (Exponent): 数の大きさを表し、基数（通常は2）の何乗であるかを示します。
  • 仮数部 (Mantissa/Significand/Fraction): 数の有効数字を表します。

この表現により、非常に広い範囲の数を表現できますが、すべての実数を正確に表現できるわけではありません。特に、2のべき乗ではない分数（例: 0.1）などは、2進数では無限小数になるため、丸め誤差が生じます。

対数関数 (Logarithm Function)

対数関数log_b(x)は、「bを何乗するとxになるか」を示す関数です。 このコミットで扱われるLog2(x)は、底が2の対数、すなわちlog_2(x)を意味します。

対数の性質として、以下の関係があります。 log_b(x) = log_c(x) / log_c(b) 特に、自然対数ln(x)（底がネイピア数e）や常用対数log_10(x)（底が10）を用いて、log_2(x)は以下のように計算できます。 log_2(x) = ln(x) / ln(2) Go言語のmathパッケージでは、Log(x)が自然対数ln(x)を、Ln2がln(2)の定数を表します。したがって、従来のLog2の実装はLog(x) * (1 / Ln2)となっていました。

Frexp関数

Frexp(x)関数は、浮動小数点数xを、x = frac * 2^expの形式に分解します。

  • frac (fraction): 0.5 <= |frac| < 1.0 の範囲にある仮数部（分数部）。
  • exp (exponent): 整数である指数部。

この関数は、浮動小数点数の内部表現を理解し、仮数部と指数部を分離して操作する際に非常に有用です。特に、2のべき乗の場合、x = 2^Nであれば、fracは0.5または1.0（正規化の仕方による）、expはNに近い値になります。

Ldexp関数

Ldexp(frac, exp)関数は、frac * 2^expを計算し、浮動小数点数を再構築します。これはFrexpの逆操作にあたります。テストコードでLdexp(1, i)が使われているのは、正確な2のべき乗2^iを生成するためです。

技術的詳細

このコミットの核心は、Log2(x)の計算方法を、単純なLog(x) * (1 / Ln2)から、Frexp関数を利用したよりロバストな方法に変更した点にあります。

従来のLog2(x)の実装は、Log(x)（自然対数）を計算し、それを1/Ln2（1/ln(2)）で乗算していました。この方法では、Log(x)の計算自体が浮動小数点演算の誤差を含み、さらに1/Ln2も浮動小数点定数であるため、これらの誤差が累積して最終的なLog2の結果に影響を与えていました。特に、xが厳密な2のべき乗（例: 2, 4, 8など）である場合でも、Log(x)が厳密なln(2^n) = n * ln(2)とならず、わずかな誤差を含むため、結果としてLog2(x)が厳密な整数値nを返さないという問題が生じていました。

新しい実装では、まず入力xをFrexp(x)によって仮数部fracと指数部expに分解します。 x = frac * 2^exp

この分解を利用すると、log_2(x)は次のように書き換えられます。 log_2(x) = log_2(frac * 2^exp) log_2(x) = log_2(frac) + log_2(2^exp) log_2(x) = log_2(frac) + exp

ここで、log_2(frac)はLog(frac) * (1 / Ln2)として計算されます。 したがって、新しいLog2の実装は以下のようになります。 Log2(x) = Log(frac) * (1 / Ln2) + float64(exp)

このアプローチの利点は、expが整数であるため、float64(exp)の部分は誤差なく正確に加算される点です。fracは0.5 <= |frac| < 1.0の範囲に正規化された値であり、この範囲でのLog(frac)の計算は、元のLog(x)の計算よりも相対的に精度が安定している可能性があります。 特に、xが厳密な2のべき乗の場合、fracは0.5または1.0（Frexpの実装による）となり、Log(frac)は正確な値（ln(0.5)またはln(1.0)）を返すか、非常に小さな誤差しか含まないため、最終的なLog2の結果はexpに非常に近い、あるいは厳密にexp（整数）となることが期待されます。これにより、2のべき乗に対するLog2の計算が正確になることが保証されます。

コミットメッセージにある「We could do a multiprecision approximation for the rest of the answer too, but this seems like it should be good enough.」という記述は、Log(frac) * (1 / Ln2)の部分についても、さらに高精度な計算（多倍長精度演算など）を適用することで、より一般的な浮動小数点数に対するLog2の精度を向上させる可能性を示唆していますが、このコミットでは2のべき乗に対する正確性を優先し、そこまでの対応は行わないという判断がなされています。

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

src/pkg/math/log10.go

--- a/src/pkg/math/log10.go
+++ b/src/pkg/math/log10.go
@@ -17,5 +17,6 @@ func log10(x float64) float64 {
 func Log2(x float64) float64
 
 func log2(x float64) float64 {
-	return Log(x) * (1 / Ln2)
+	frac, exp := Frexp(x)
+	return Log(frac)*(1/Ln2) + float64(exp)
 }

src/pkg/math/all_test.go

--- a/src/pkg/math/all_test.go
+++ b/src/pkg/math/all_test.go
@@ -2281,6 +2281,13 @@ func TestLog2(t *testing.T) {
 			t.Errorf("Log2(%g) = %g, want %g", vflogSC[i], f, logSC[i])
 		}
 	}
+	for i := -1074; i <= 1023; i++ {
+		f := Ldexp(1, i)
+		l := Log2(f)
+		if l != float64(i) {
+			t.Errorf("Log2(2**%d) = %g, want %d", i, l, i)
+		}
+	}
 }
 
 func TestModf(t *testing.T) {

コアとなるコードの解説

src/pkg/math/log10.go の変更

  • 変更前: func log2(x float64) float64 { return Log(x) * (1 / Ln2) }

    • これは、log_2(x) = ln(x) / ln(2)という数学的定義を直接浮動小数点演算で実装したものです。Log(x)は自然対数、Ln2はln(2)の定数です。この方法では、Log(x)と1/Ln2の計算における浮動小数点誤差が累積し、特に2のべき乗に対して正確な整数値が得られない問題がありました。

  • 変更後:

    func log2(x float64) float64 {
	frac, exp := Frexp(x)
	return Log(frac)*(1/Ln2) + float64(exp)
}
    • frac, exp := Frexp(x): 入力xをFrexp関数を使って、仮数部fracと指数部expに分解します。x = frac * 2^expの関係が成り立ちます。expは整数です。
    • return Log(frac)*(1/Ln2) + float64(exp):
      • Log(frac)*(1/Ln2): これはlog_2(frac)を計算する部分です。fracは0.5 <= |frac| < 1.0の範囲に正規化されているため、この部分の計算は比較的安定しています。
      • + float64(exp): expは整数なので、float64(exp)とすることで、誤差なく浮動小数点数に変換され、log_2(frac)に加算されます。
    • この新しい計算式により、log_2(x) = log_2(frac) + expという関係が利用され、特にxが2のべき乗の場合（例: x = 2^N）、fracが0.5または1.0となり、Log(frac)が正確な値（ln(0.5)またはln(1.0)）を返すため、最終的な結果が正確な整数Nに近づく、あるいは厳密にNとなることが保証されます。

src/pkg/math/all_test.go の変更

  • 追加されたテストケース: 
    	for i := -1074; i <= 1023; i++ {
		f := Ldexp(1, i)
		l := Log2(f)
		if l != float64(i) {
			t.Errorf("Log2(2**%d) = %g, want %d", i, l, i)
		}
	}
    • このループは、iを-1074から1023まで変化させながらテストを実行します。この範囲は、float64型で表現可能な正規化された数の指数部の典型的な範囲をカバーしています。
    • f := Ldexp(1, i): Ldexp(1, i)は1 * 2^i、つまり厳密な2のべき乗2^iを生成します。これにより、テスト対象の入力が正確な2のべき乗であることが保証されます。
    • l := Log2(f): 修正されたLog2関数を呼び出し、2^iの対数を計算します。
    • if l != float64(i): 計算結果lが期待される整数値iと厳密に一致するかどうかをチェックします。float64(i)とすることで、整数iを浮動小数点数に変換して比較しています。
    • t.Errorf(...): もし結果が一致しない場合、エラーメッセージを出力します。

この追加されたテストケースは、コミットの目的である「2のべき乗が正確な答えを返すことを保証する」という点を直接検証するためのものです。これにより、変更が意図通りに機能していることが確認できます。

関連リンク

参考にした情報源リンク

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

このコミットは、Go言語のmathパッケージにおけるLog2関数の実装を改善し、特に2のべき乗に対する計算結果の精度を保証することを目的としています。具体的には、浮動小数点数の指数部を分離して処理することで、Log2(2^n)が正確にnを返すように修正されています。

コミット

commit a3677b5f223db6ccadf26f81a751c4f8c8c0eaf9
Author: Russ Cox <rsc@golang.org>
Date:   Thu Dec 20 12:23:27 2012 -0500

    math: handle exponent separately in Log2
    
    This guarantees that powers of two return exact answers.
    
    We could do a multiprecision approximation for the
    rest of the answer too, but this seems like it should be
    good enough.
    
    Fixes #4567.
    
    R=golang-dev, iant, remyoudompheng
    CC=golang-dev
    https://golang.org/cl/6943074

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

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

元コミット内容

このコミットは、Log2関数が2のべき乗に対して正確な結果を返すように修正します。

コミットメッセージの要約:

  • Log2関数で指数部を個別に処理する。
  • これにより、2のべき乗が正確な答えを返すことが保証される。
  • 残りの部分についても多倍長精度近似を行うことは可能だが、現状で十分と判断。
  • Issue #4567 を修正。

変更の背景

この変更の背景には、浮動小数点演算における精度の問題、特にLog2関数が2のべき乗（例: 2, 4, 8, 16...）に対して期待される整数値を正確に返さないという問題がありました。浮動小数点数はその性質上、多くの実数を正確に表現できず、近似値として扱われます。しかし、2のべき乗の対数（底2）は常に整数になるため、これらの値については正確な結果が強く求められます。

Issue #4567（"math: Log2(2**N) should be N"）では、Log2(2**N)がNを返さないという具体的な問題が報告されていました。例えば、Log2(1)が0ではなく4.9406564584124654e-324のような非常に小さい非ゼロ値を返したり、Log2(2)が1ではなく0.9999999999999999のような値になったりすることが指摘されていました。これは、Log2(x)がLog(x) * (1 / Ln2)として計算されていたため、Log(x)と1/Ln2の浮動小数点近似誤差が累積して発生していました。

この問題は、特に数値計算や科学技術計算において、2のべき乗が頻繁に登場し、その対数が正確であることが前提とされる場合に、予期せぬ誤差やバグを引き起こす可能性がありました。そのため、このコミットは、Log2関数が2のべき乗に対して厳密な結果を返すようにすることで、関数の信頼性と予測可能性を高めることを目的としています。

前提知識の解説

浮動小数点数 (Floating-Point Numbers)

コンピュータにおける浮動小数点数は、実数を近似的に表現するための形式です。IEEE 754規格が広く用いられており、Go言語のfloat64型もこれに準拠しています。浮動小数点数は通常、符号部、指数部、仮数部（または分数部）の3つの要素で構成されます。

  • 符号部 (Sign): 数の正負を表します。
  • 指数部 (Exponent): 数の大きさを表し、基数（通常は2）の何乗であるかを示します。
  • 仮数部 (Mantissa/Significand/Fraction): 数の有効数字を表します。

この表現により、非常に広い範囲の数を表現できますが、すべての実数を正確に表現できるわけではありません。特に、2のべき乗ではない分数（例: 0.1）などは、2進数では無限小数になるため、丸め誤差が生じます。

対数関数 (Logarithm Function)

対数関数log_b(x)は、「bを何乗するとxになるか」を示す関数です。 このコミットで扱われるLog2(x)は、底が2の対数、すなわちlog_2(x)を意味します。

対数の性質として、以下の関係があります。 log_b(x) = log_c(x) / log_c(b) 特に、自然対数ln(x)（底がネイピア数e）や常用対数log_10(x)（底が10）を用いて、log_2(x)は以下のように計算できます。 log_2(x) = ln(x) / ln(2) Go言語のmathパッケージでは、Log(x)が自然対数ln(x)を、Ln2がln(2)の定数を表します。したがって、従来のLog2の実装はLog(x) * (1 / Ln2)となっていました。

Frexp関数

Frexp(x)関数は、浮動小数点数xを、x = frac * 2^expの形式に分解します。

  • frac (fraction): 0.5 <= |frac| < 1.0 の範囲にある仮数部（分数部）。
  • exp (exponent): 整数である指数部。

この関数は、浮動小数点数の内部表現を理解し、仮数部と指数部を分離して操作する際に非常に有用です。特に、2のべき乗の場合、x = 2^Nであれば、fracは0.5または1.0（正規化の仕方による）、expはNに近い値になります。

Ldexp関数

Ldexp(frac, exp)関数は、frac * 2^expを計算し、浮動小数点数を再構築します。これはFrexpの逆操作にあたります。テストコードでLdexp(1, i)が使われているのは、正確な2のべき乗2^iを生成するためです。

技術的詳細

このコミットの核心は、Log2(x)の計算方法を、単純なLog(x) * (1 / Ln2)から、Frexp関数を利用したよりロバストな方法に変更した点にあります。

従来のLog2(x)の実装は、Log(x)（自然対数）を計算し、それを1/Ln2（1/ln(2)）で乗算していました。この方法では、Log(x)の計算自体が浮動小数点演算の誤差を含み、さらに1/Ln2も浮動小数点定数であるため、これらの誤差が累積して最終的なLog2の結果に影響を与えていました。特に、xが厳密な2のべき乗（例: 2, 4, 8など）である場合でも、Log(x)が厳密なln(2^n) = n * ln(2)とならず、わずかな誤差を含むため、結果としてLog2(x)が厳密な整数値nを返さないという問題が生じていました。

新しい実装では、まず入力xをFrexp(x)によって仮数部fracと指数部expに分解します。 x = frac * 2^exp

この分解を利用すると、log_2(x)は次のように書き換えられます。 log_2(x) = log_2(frac * 2^exp) log_2(x) = log_2(frac) + log_2(2^exp) log_2(x) = log_2(frac) + exp

ここで、log_2(frac)はLog(frac) * (1 / Ln2)として計算されます。 したがって、新しいLog2の実装は以下のようになります。 Log2(x) = Log(frac) * (1 / Ln2) + float64(exp)

このアプローチの利点は、expが整数であるため、float64(exp)の部分は誤差なく正確に加算される点です。fracは0.5 <= |frac| < 1.0の範囲に正規化された値であり、この範囲でのLog(frac)の計算は、元のLog(x)の計算よりも相対的に精度が安定している可能性があります。 特に、xが厳密な2のべき乗の場合、fracは0.5または1.0（Frexpの実装による）となり、Log(frac)は正確な値（ln(0.5)またはln(1.0)）を返すか、非常に小さな誤差しか含まないため、最終的なLog2の結果はexpに非常に近い、あるいは厳密にexp（整数）となることが期待されます。これにより、2のべき乗に対するLog2の計算が正確になることが保証されます。

コミットメッセージにある「We could do a multiprecision approximation for the rest of the answer too, but this seems like it should be good enough.」という記述は、Log(frac) * (1 / Ln2)の部分についても、さらに高精度な計算（多倍長精度演算など）を適用することで、より一般的な浮動小数点数に対するLog2の精度を向上させる可能性を示唆していますが、このコミットでは2のべき乗に対する正確性を優先し、そこまでの対応は行わないという判断がなされています。

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

src/pkg/math/log10.go

--- a/src/pkg/math/log10.go
+++ b/src/pkg/math/log10.go
@@ -17,5 +17,6 @@ func log10(x float64) float64 {
 func Log2(x float64) float64
 
 func log2(x float64) float64 {
-	return Log(x) * (1 / Ln2)
+	frac, exp := Frexp(x)
+	return Log(frac)*(1/Ln2) + float64(exp)
 }

src/pkg/math/all_test.go

--- a/src/pkg/math/all_test.go
+++ b/src/pkg/math/all_test.go
@@ -2281,6 +2281,13 @@ func TestLog2(t *testing.T) {
 			t.Errorf("Log2(%g) = %g, want %g", vflogSC[i], f, logSC[i])
 		}
 	}
+	for i := -1074; i <= 1023; i++ {
+		f := Ldexp(1, i)
+		l := Log2(f)
+		if l != float64(i) {
+			t.Errorf("Log2(2**%d) = %g, want %d", i, l, i)
+		}
+	}
 }
 
 func TestModf(t *testing.T) {

コアとなるコードの解説

src/pkg/math/log10.go の変更

  • 変更前: func log2(x float64) float64 { return Log(x) * (1 / Ln2) }

    • これは、log_2(x) = ln(x) / ln(2)という数学的定義を直接浮動小数点演算で実装したものです。Log(x)は自然対数、Ln2はln(2)の定数です。この方法では、Log(x)と1/Ln2の計算における浮動小数点誤差が累積し、特に2のべき乗に対して正確な整数値が得られない問題がありました。

  • 変更後:

    func log2(x float64) float64 {
	frac, exp := Frexp(x)
	return Log(frac)*(1/Ln2) + float64(exp)
}
    • frac, exp := Frexp(x): 入力xをFrexp関数を使って、仮数部fracと指数部expに分解します。x = frac * 2^expの関係が成り立ちます。expは整数です。
    • return Log(frac)*(1/Ln2) + float64(exp):
      • Log(frac)*(1/Ln2): これはlog_2(frac)を計算する部分です。fracは0.5 <= |frac| < 1.0の範囲に正規化されているため、この部分の計算は比較的安定しています。
      • + float64(exp): expは整数なので、float64(exp)とすることで、誤差なく浮動小数点数に変換され、log_2(frac)に加算されます。
    • この新しい計算式により、log_2(x) = log_2(frac) + expという関係が利用され、特にxが2のべき乗の場合（例: x = 2^N）、fracが0.5または1.0となり、Log(frac)が正確な値（ln(0.5)またはln(1.0)）を返すため、最終的な結果が正確な整数Nに近づく、あるいは厳密にNとなることが保証されます。

src/pkg/math/all_test.go の変更

  • 追加されたテストケース: 
    	for i := -1074; i <= 1023; i++ {
		f := Ldexp(1, i)
		l := Log2(f)
		if l != float64(i) {
			t.Errorf("Log2(2**%d) = %g, want %d", i, l, i)
		}
	}
    • このループは、iを-1074から1023まで変化させながらテストを実行します。この範囲は、float64型で表現可能な正規化された数の指数部の典型的な範囲をカバーしています。
    • f := Ldexp(1, i): Ldexp(1, i)は1 * 2^i、つまり厳密な2のべき乗2^iを生成します。これにより、テスト対象の入力が正確な2のべき乗であることが保証されます。
    • l := Log2(f): 修正されたLog2関数を呼び出し、2^iの対数を計算します。
    • if l != float64(i): 計算結果lが期待される整数値iと厳密に一致するかどうかをチェックします。float64(i)とすることで、整数iを浮動小数点数に変換して比較しています。
    • t.Errorf(...): もし結果が一致しない場合、エラーメッセージを出力します。

この追加されたテストケースは、コミットの目的である「2のべき乗が正確な答えを返すことを保証する」という点を直接検証するためのものです。これにより、変更が意図通りに機能していることが確認できます。

関連リンク

参考にした情報源リンク