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

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

このコミットは、Goコンパイラ（gc）における浮動小数点演算の実装を、ネイティブのdouble型から、カスタムの多倍長浮動小数点数表現へと根本的に変更するものです。これにより、コンパイル時の定数評価において、より高い精度と正確性が実現されます。

コミット

commit 3fa46106017b0eed128e83d4ce084c43efc14d5f
Author: Ken Thompson <ken@golang.org>
Date:   Mon Dec 1 17:22:05 2008 -0800

    multi precision floating point
    
    R=r
    OCL=20185
    CL=20185

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

https://github.com/golang/go/commit/3fa46106017b0eed128e83d4ce084c43efc14d5f

元コミット内容

このコミットの目的は、「多倍長浮動小数点数」のサポートをGoコンパイラに導入することです。具体的には、コンパイラ内部での浮動小数点定数の扱いを、標準のdouble型に依存するのではなく、ソフトウェアで実装された任意精度（多倍長）の浮動小数点演算に切り替えるものです。

変更の背景

Go言語の初期開発段階において、コンパイラは定数式の評価を行う必要がありました。特に浮動小数点定数については、その評価結果が言語仕様に厳密に準拠し、かつプラットフォームに依存しない一貫した振る舞いを保証することが重要です。

従来のGoコンパイラ（gc）では、浮動小数点定数の内部表現や演算にC言語のdouble型を直接使用していました。しかし、double型はIEEE 754標準に準拠しているものの、その精度は有限であり、特定の計算において丸め誤差が発生する可能性があります。コンパイラが定数畳み込み（constant folding）を行う際、これらの丸め誤差が蓄積されると、予期せぬ結果や、異なるアーキテクチャ間での挙動の不一致を引き起こす可能性がありました。

このコミットの背景には、以下のような課題認識があったと考えられます。

  1. 精度の問題: double型では表現できない、あるいは計算過程で精度が失われるような浮動小数点定数（例: 非常に大きな数、非常に小さな数、循環小数など）を正確に扱う必要性。
  2. 移植性の問題: 異なるCPUアーキテクチャやOS環境において、double型の浮動小数点演算の振る舞いが微妙に異なる可能性があり、コンパイラの定数評価結果の一貫性を損なう恐れがあった。
  3. 言語仕様の厳密性: Go言語の設計思想として、言語の振る舞いは厳密に定義され、予測可能であるべきという原則があります。定数評価もその例外ではなく、常に同じ結果を返すことが求められます。

これらの課題を解決するため、Ken Thompson氏によって、コンパイラ内部で独自の多倍長浮動小数点数演算ライブラリを実装し、定数評価に利用するというアプローチが採用されました。これにより、Goコンパイラは、ネイティブの浮動小数点ハードウェアに依存せず、ソフトウェア的に高い精度で浮動小数点定数を扱うことが可能になります。

前提知識の解説

このコミットを理解するためには、以下の概念が前提となります。

  1. 浮動小数点数 (Floating-Point Numbers): コンピュータで実数を表現する方法の一つで、仮数部（significand/mantissa）と指数部（exponent）に分けて表現します。IEEE 754標準が広く用いられており、float（単精度）やdouble（倍精度）といった型があります。有限のビット数で表現されるため、すべての実数を正確に表現できるわけではなく、丸め誤差が発生します。

  2. 多倍長演算 (Arbitrary-Precision Arithmetic / BigNum Arithmetic): コンピュータのネイティブなデータ型（例: int, long, double）が持つビット数に制限されず、任意の桁数（精度）の数値を扱うための演算手法です。通常、数値は配列やリストなどのデータ構造で表現され、加算、減算、乗算、除算などの演算はソフトウェアで実装されます。これにより、ネイティブ型では扱えない非常に大きな数や、高い精度の計算が可能になります。

  3. コンパイラの定数畳み込み (Constant Folding): コンパイラの最適化手法の一つで、コンパイル時に値が確定する式（定数式）を事前に計算し、その結果で置き換えることです。例えば、2 + 3という式があれば、コンパイラはこれを5に置き換えます。これにより、実行時の計算コストを削減し、プログラムのパフォーマンスを向上させることができます。浮動小数点定数についても同様に適用されますが、その精度が問題となることがあります。

  4. Goコンパイラ (gc): Go言語の公式コンパイラの一つで、Go言語自体で書かれています。初期のGoコンパイラはC言語で書かれており、このコミットはそのC言語時代のgcに対する変更です。src/cmd/gcディレクトリ以下にそのソースコードがあります。

  5. fmtパッケージのfmtinstall: Go言語のfmtパッケージ（あるいはその前身となるC言語時代のフォーマットライブラリ）における、カスタムのフォーマット動詞（verb）を登録するためのメカニズムです。printfのような関数で%dや%sのように使われる%に続く文字を「フォーマット動詞」と呼び、これに独自の型を対応させることで、その型の値を特定の形式で文字列に変換できるようになります。

技術的詳細

このコミットの核心は、Goコンパイラ内部で浮動小数点数を表現するための新しいデータ構造Mpfltと、それに対する多倍長演算の実装です。

1. Mpflt構造体の再定義

変更前はdouble val;とuchar ovf;を持っていたMpflt構造体が、以下のように大幅に変更されました。

typedef	struct	Mpflt	Mpflt;
struct	Mpflt
{
	Mpint	val;  // 仮数部を多倍長整数Mpintで表現
	short	exp;  // 指数部
};
  • Mpint val;: 浮動小数点数の仮数部（mantissa）を、新たに定義された多倍長整数型Mpintで保持します。これにより、仮数部の精度がネイティブのdouble型の53ビット（倍精度）に制限されず、Mpprec * Mpscaleビット（このコミットでは16 * 29 = 464ビット）という高い精度で表現できるようになります。
  • short exp;: 指数部を保持します。

2. Mpint構造体の変更と多倍長整数の基盤

Mpint構造体も変更され、多倍長整数としての機能が強化されています。

typedef	struct	Mpint	Mpint;
struct	Mpint
{
	long	a[Mpprec]; // 数値をMpprec個のlong型配列で表現
	uchar	neg;       // 符号 (負の場合1)
	uchar	ovf;       // オーバーフローフラグ
};
  • long a[Mpprec];: 数値をMpprec個のlong型配列で表現します。各longはMpscaleビット（29ビット）の「桁」を表します。Mpprecが10から16に増えたことで、表現できる数値の範囲と精度が向上しています。
  • Mpscale: 各配列要素が保持するビット数（29）。1L<<Mpscaleが基数となります。
  • Mpprec: 仮数部を構成するlong配列の要素数（16）。
  • Mpnorm: 正規化された浮動小数点数の仮数部が持つべき有効なワード数（Mpprec - 1）。

3. 新しい多倍長浮動小数点演算関数の導入

mparith1.c, mparith2.c, mparith3.cといったファイル群に、MpfltとMpintを操作するための多数の新しい関数が追加・修正されています。

  • mpshiftfix(Mpint *a, int s): Mpint値をsビットだけシフトする汎用関数。正のsで左シフト、負のsで右シフトを行います。これにより、従来のmplshfixfixやmprshfixfix内の冗長なループが置き換えられました。
  • mpmulfract(Mpint *a, Mpint *b): Mpint型の仮数部同士の乗算を行います。これは浮動小数点数の乗算の核心部分です。
  • mpdivfract(Mpint *a, Mpint *b): Mpint型の仮数部同士の除算を行います。これは浮動小数点数の除算の核心部分です。
  • sigfig(Mpflt *a): Mpfltの仮数部における最上位の非ゼロワードのインデックスを返します。正規化処理に利用されます。
  • mpnorm(Mpflt *a): Mpflt値を正規化します。仮数部の最上位の非ゼロワードをMpnormの位置にシフトし、それに応じて指数部を調整します。これにより、浮動小数点数の表現が一意になり、比較や演算が容易になります。
  • mpaddfltflt, mpmulfltflt, mpdivfltflt: これらの関数は、Mpflt構造体に対する加算、乗算、除算を実装しています。内部ではMpintに対するmpshiftfix, mpaddfixfix, mpmulfract, mpdivfractなどの関数を組み合わせて、多倍長演算を実現しています。特に、指数部が異なる場合の仮数部のシフト調整や、乗算・除算後の指数部の計算が重要です。
  • mpgetflt(Mpflt *a): Mpflt値をC言語のdouble型に変換します。これは、最終的な結果をネイティブ型で利用する場合に必要となりますが、変換時に精度が失われる可能性があります。
  • mpmovecflt(Mpflt *a, double c): C言語のdouble値をMpflt型に変換します。frexp関数（浮動小数点数を仮数と指数に分解する）を利用して、double値をMpfltのval（Mpint）とexpに分解し、多倍長表現に変換します。
  • mpatoflt(Mpflt *a, char *as): 文字列からMpflt型への変換を行います。従来のstrtod（C標準ライブラリの文字列からdoubleへの変換）の使用を廃止し、独自の多倍長演算を用いて文字列をMpfltにパースするロジックに置き換えられました。これにより、パース段階での精度損失を防ぎます。
  • Fconv(Fmt *fp): fmtパッケージ（またはその前身）のカスタムフォーマット動詞%Fを実装します。これにより、Mpflt型の値を人間が読める形式（例: (仮数*2^指数)または(仮数/2^指数)）で出力できるようになります。これはデバッグや内部状態の確認に非常に有用です。

4. ビルドシステムとヘッダファイルの変更

  • src/cmd/gc/Makefile: 新しいヘッダファイルmparith.hがHFILESに追加されました。これは、多倍長演算関連の関数や構造体の宣言をまとめたものと推測されます。
  • src/cmd/gc/go.h: MpintとMpfltの構造体定義が更新され、新しい多倍長演算関数のプロトタイプ宣言が追加されました。

5. デバッグ機能の変更

  • go.hでDebugマクロがMpdebugに変更され、初期値が0に設定されました。これは、多倍長浮動小数点演算のデバッグ出力を制御するためのフラグです。mparith3.cのmpaddfltflt、mpmulfltflt、mpdivfltflt、mpmovecflt、mptestflt関数内でMpdebugが1の場合にデバッグ出力を行うコードが追加されており、開発者が演算の途中経過を確認できるようになっています。

これらの変更により、Goコンパイラは、コンパイル時に浮動小数点定数を扱う際に、より高い精度とプラットフォーム非依存性を実現できるようになりました。これは、言語の厳密な仕様と移植性を保証する上で非常に重要な基盤となります。

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

このコミットにおけるコアとなるコードの変更は、主に以下のファイルと関数に集中しています。

  1. src/cmd/gc/go.h:

    • MpintとMpflt構造体の定義が、多倍長整数と多倍長浮動小数点数に対応するように根本的に変更されました。
    • Mpprec（仮数部のワード数）が10から16に増加しました。
    • 新しい多倍長演算関数のプロトタイプ宣言が多数追加されました（例: mpmulfract, mpdivfract, mpshiftfix, mpnorm, Fconv）。

  2. src/cmd/gc/mparith1.c:

    • mpatoflt関数が全面的に書き換えられ、C標準ライブラリのstrtodに依存せず、独自の多倍長浮動小数点数パースロジックが実装されました。これにより、文字列からMpfltへの変換精度が向上しました。
    • mppow10flt関数が追加され、10のべき乗を多倍長浮動小数点数で計算するようになりました。
    • mpmovefixflt関数が、MpintからMpfltへの変換ロジックを新しい構造体に合わせて変更しました。
    • Fconv関数が追加され、Mpflt型の値をフォーマットするためのカスタムフォーマッタとして機能します。

  3. src/cmd/gc/mparith2.c:

    • mpshiftfix関数が追加されました。これは、多倍長整数Mpintをビット単位で効率的にシフトするための汎用関数であり、他の多倍長演算の基盤となります。
    • mpmulfract関数が追加されました。これは、多倍長整数の仮数部同士の乗算を実装しています。
    • mpdivfract関数が追加されました。これは、多倍長整数の仮数部同士の除算を実装しています。
    • 既存のmplshfixfixとmprshfixfix関数が、新しく追加されたmpshiftfix関数を利用するように変更されました。

  4. src/cmd/gc/mparith3.c:

    • sigfig関数が追加されました。これは、Mpfltの仮数部における最上位の非ゼロワードを特定するために使用されます。
    • mpnorm関数が追加されました。これは、Mpflt値を正規化し、仮数部と指数部を調整して一貫した表現を保証します。
    • mpaddfltflt, mpmulfltflt, mpdivfltfltといった主要な浮動小数点演算関数が、新しいMpflt構造体とMpintベースの多倍長演算関数（mpaddfixfix, mpmulfract, mpdivfract, mpshiftfixなど）を利用するように全面的に書き換えられました。
    • mpgetflt関数とmpmovecflt関数が、Mpfltとdouble間の変換ロジックを新しい多倍長表現に合わせて変更しました。特にmpmovecfltはfrexpを利用してdoubleを多倍長表現に分解します。

これらの変更は、Goコンパイラが浮動小数点定数を扱う方法の根本的なパラダイムシフトを示しており、コンパイラの正確性と移植性を大幅に向上させるものです。

コアとなるコードの解説

ここでは、特に重要な変更点であるMpfltの構造と、それを用いた主要な演算の概念を解説します。

Mpflt構造体と多倍長浮動小数点数の表現

// src/cmd/gc/go.h
typedef	struct	Mpflt	Mpflt;
struct	Mpflt
{
	Mpint	val;  // 仮数部 (mantissa)
	short	exp;  // 指数部 (exponent)
};

Mpfltは、浮動小数点数を「仮数部」と「指数部」に分けて表現します。

  • val (仮数部): Mpint型で、数値の有効数字部分を多倍長整数として保持します。これにより、double型が持つ53ビットの仮数部よりもはるかに多くのビット数（Mpprec * Mpscale = 16 * 29 = 464ビット）で精度を表現できます。
  • exp (指数部): short型で、仮数部をどれだけシフトすれば実際の値になるかを示します。これは2のべき乗の指数として機能します。

この表現は、一般的な浮動小数点数表現（例: IEEE 754）と似ていますが、仮数部が固定長のバイナリ表現ではなく、可変長（多倍長）の整数で表現される点が異なります。

mpnorm関数による正規化

// src/cmd/gc/mparith3.c
void
mpnorm(Mpflt *a)
{
	int s;

	s = sigfig(a); // 最上位の非ゼロワードを検出
	if(s == 0) {
		// zero
		a->exp = 0;
		a->val.neg = 0;
		return;
	}
	s = (Mpnorm-s) * Mpscale; // 正規化に必要なシフト量
	mpshiftfix(&a->val, s);   // 仮数部をシフト
	a->exp -= s;              // 指数部を調整
}

mpnormは、Mpflt値を「正規化」する重要な関数です。正規化とは、浮動小数点数の表現を一意にするための処理で、仮数部の最上位ビットが常に特定の場所に位置するように調整することです。

  • sigfig(a): 仮数部a->valの最上位の非ゼロワード（long型の要素）がどこにあるかを検出します。
  • s = (Mpnorm-s) * Mpscale;: 仮数部をMpnorm（Mpprec - 1番目のワード）の位置にシフトするために必要なビット数を計算します。
  • mpshiftfix(&a->val, s);: 計算されたビット数だけ仮数部をシフトします。
  • a->exp -= s;: 仮数部をシフトした分、値が変わらないように指数部を調整します。

この正規化により、例えば0.5 * 2^10と1.0 * 2^9のように同じ値を異なる仮数部と指数部で表現するのを防ぎ、比較や演算を正確に行えるようになります。

mpaddfltflt関数による加算

// src/cmd/gc/mparith3.c
void
mpaddfltflt(Mpflt *a, Mpflt *b)
{
	int sa, sb, s;
	Mpflt c;

	// ... (ゼロ値のハンドリング、デバッグ出力) ...

	s = a->exp - b->exp; // 指数部の差を計算
	if(s > 0) {
		// aの指数部が大きい場合、bの仮数部を右シフトして指数部をaに合わせる
		mpmovefltflt(&c, b);
		mpshiftfix(&c.val, -s); // bの仮数部を右シフト
		mpaddfixfix(&a->val, &c.val); // 仮数部同士を加算
	} else if(s < 0) {
		// bの指数部が大きい場合、aの仮数部を右シフトして指数部をbに合わせる
		mpshiftfix(&a->val, s); // aの仮数部を右シフト (sは負の値なので実質右シフト)
		a->exp -= s;            // aの指数部をbに合わせる
		mpaddfixfix(&a->val, &b->val); // 仮数部同士を加算
	} else {
		// 指数部が同じ場合、そのまま仮数部同士を加算
		mpaddfixfix(&a->val, &b->val);
	}

	mpnorm(a); // 結果を正規化
	// ... (デバッグ出力) ...
}

浮動小数点数の加算は、指数部を揃えてから仮数部を加算するという手順で行われます。

  1. 指数部の比較: a->expとb->expを比較し、大きい方に揃えます。
  2. 仮数部のシフト: 指数部を揃えるために、小さい方の指数部を持つ数値の仮数部を右シフトします。例えば、A * 2^EaとB * 2^EbでEa > Ebの場合、BをB * 2^(Eb-Ea)に変換し、A * 2^Ea + (B * 2^(Eb-Ea)) * 2^Eaとして加算します。このシフトはmpshiftfixで行われます。
  3. 仮数部の加算: 指数部が揃った後、mpaddfixfixを使って仮数部（Mpint）同士を加算します。
  4. 結果の正規化: 加算結果をmpnormで正規化します。

mpmulfltflt関数による乗算

// src/cmd/gc/mparith3.c
void
mpmulfltflt(Mpflt *a, Mpflt *b)
{
	// ... (ゼロ値のハンドリング、デバッグ出力) ...

	mpmulfract(&a->val, &b->val); // 仮数部同士を乗算
	// 指数部の計算: (aの指数 + bの指数) + (Mpscale * Mpprec - 1)
	// Mpscale * Mpprec - 1 は、仮数部が正規化された状態での基底の調整項
	a->exp = (a->exp + b->exp) + Mpscale*Mpprec - 1; 

	mpnorm(a); // 結果を正規化
	// ... (デバッグ出力) ...
}

浮動小数点数の乗算は、仮数部同士を乗算し、指数部同士を加算するという比較的単純な手順で行われます。

  1. 仮数部の乗算: mpmulfractを使って仮数部（Mpint）同士を乗算します。
  2. 指数部の加算: a->expとb->expを加算します。さらに、仮数部の表現方法（正規化の基準）に起因するオフセット（Mpscale*Mpprec - 1）を加えます。
  3. 結果の正規化: 乗算結果をmpnormで正規化します。

mpdivfltflt関数による除算

// src/cmd/gc/mparith3.c
void
mpdivfltflt(Mpflt *a, Mpflt *b)
{
	// ... (ゼロ除算のハンドリング、ゼロ値のハンドリング、デバッグ出力) ...

	// bを正規化し、仮数部を最上位にシフト（除算の精度を上げるため）
	mpmovefltflt(&c, b);
	mpshiftfix(&c.val, Mpscale); // bの仮数部を左シフト

	mpdivfract(&a->val, &c.val); // 仮数部同士を除算
	// 指数部の計算: (aの指数 - cの指数) - Mpscale*(Mpprec-1) + 1
	// Mpscale*(Mpprec-1) + 1 は、仮数部が正規化された状態での基底の調整項
	a->exp = (a->exp-c.exp) - Mpscale*(Mpprec-1) + 1;

	mpnorm(a); // 結果を正規化
	// ... (デバッグ出力) ...
}

浮動小数点数の除算は、仮数部同士を除算し、指数部同士を減算するという手順で行われます。

  1. 除数の調整: 除数bの仮数部をmpshiftfixで左シフトし、除算の精度を向上させます。
  2. 仮数部の除算: mpdivfractを使って仮数部（Mpint）同士を除算します。
  3. 指数部の減算: a->expからc.exp（調整後のbの指数）を減算します。さらに、仮数部の表現方法に起因するオフセット（Mpscale*(Mpprec-1) + 1）を調整します。
  4. 結果の正規化: 除算結果をmpnormで正規化します。

これらの関数は、多倍長整数演算のプリミティブ（mpaddfixfix, mpmulfract, mpdivfract, mpshiftfixなど）を組み合わせて、多倍長浮動小数点数の加減乗除を実現しています。これにより、Goコンパイラは、コンパイル時に非常に高い精度で浮動小数点定数を扱うことが可能になりました。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード (特にsrc/cmd/gcディレクトリ内のmparith*.cファイル群)
  • Go言語の初期のコミット履歴 (GitHub)
  • コンパイラの最適化に関する一般的な知識 (定数畳み込みなど)
  • 浮動小数点数演算に関する一般的な知識 (IEEE 754など)
  • 多倍長演算ライブラリの実装に関する一般的な知識
  • Ken Thompson氏の業績に関する情報 (Go言語の共同開発者)