ダブルダブル:FPUを離れることなく31桁の精度を実現
Double-double: 31 digits of precision without leaving the FPU (marekfiser.com)
要約
倍精度浮動小数点数(double)の15桁の精度では不十分な場合、2つのdoubleを結合して1つの数値として扱う「ダブルダブル」という手法があります。これにより、約31桁の精度が得られ、通常のdoubleと比較して約9倍のコストで済みます。この手法は、ヒープ割り当てや依存関係がなく、パフォーマンス面でdoubleと任意精度ライブラリの中間に位置します。本記事では、この手法を可能にするエラーフリー変換について解説し、MPFRと比較してその性能を測定し、限界についても示します。
全文翻訳
Double-double演算: 2つのdoubleから31桁の精度を
double形式の15桁の十進数精度では不十分な場合、簡単なトリックがあります。それは、2つのdoubleを結合して1つの数値として扱うことです。これにより、通常のdoubleのおよそ9倍のコストで約31桁の精度が得られます。ヒープ割り当てや依存関係なしに、パフォーマンスはdoubleと任意精度ライブラリの中間に位置します。この記事では、この形式の仕組みと背後にある数学を解説します。また、__float128およびMPFRとのベンチマークを行い、このトリックが限界を迎える箇所を示します。
1. double-doubleが埋めるギャップ#
浮動小数点型には多くの「フレーバー」があります。例えば、floatは約7桁、doubleは約15桁の十進数精度を持ちます。任意精度ライブラリは必要なだけの桁数を提供しますが、演算ごとのコストは非常に高くなります(100倍以上遅い)。「精度が少し足りない」と「桁違いに遅い」の間にはギャップがあり、私はインタラクティブなマンデルブロ集合レンダラーを実装中にそれに陥りました。このページの最上部にある画像が私の動機です。左はdouble精度、右はdouble-double精度でレンダリングされたマンデルブロ集合です。
マンデルブロ集合は有名なフラクタルで、無限に繰り返される螺旋や自身のミニコピーで満たされています。私は以前にも探求したことがあります。深く深くズームしていくと、隣接するピクセルが同じ座標に丸められるため、画像は最終的に単色のブロックに崩壊します。
図1: double精度でレンダリングされた2つの深い場所。このズームレベルでは不十分なため、醜いブロックが見えます。
図1の単色のブロックが各画像で異なる向きになっていることに注意してください。これは浮動小数点表現の仕組みによる結果です。隣接する数値間のギャップは数値の大きさに比例して増加するため、2つの座標のうち大きい方が先に解像度を失います。左の画像は(-0.74, 0.13)であり、ブロックは縦よりも横に長くなっていますが、右の画像は(-0.11, 0.92)であり、その比率は逆転しています。
「doubleより高い精度が必要」という場合の標準的な回答は、通常GMPやMPFRのような任意精度数学ライブラリを使用することです。しかし、これにはいくつかの注意点があります。
- 各値はヒープに割り当てられたデータ配列(リムと呼ばれる)へのポインタであるため、新しい数値を作成すると割り当てが発生します。割り当てを避けるために、値を再利用するように細心の注意を払う必要があります。
- ほとんどの操作はリム配列をループするため、メモリトラフィック、データ依存の分岐などが発生します。
- .NETではさらにハードルがあります。GMPとMPFRはネイティブCライブラリであるため、P/Invoke、プラットフォームごとのネイティブバイナリの配布、境界でのマーシャリングが必要になります。
したがって、より高い精度を安価に得るためのトリックは次のとおりです。
2つのdoubleを別々に保持し、それらを1つの数値として扱います。
これにより、ヒープ割り当てや依存関係なしに約31桁の精度が得られます。
このアイデアは私のオリジナルではありません。Dekkerが1971年にこれを記述しており、その構成要素はさらに古いです(詳細はさらに読むを参照)。私は、半世紀にわたるハードウェアの高速化と任意精度ライブラリの改善を経た今でも、このトリックが依然として関連性があることを自分自身(そしてあなた)に証明したかったのです。
2. double-doubleのアイデア#
浮動小数点型は、数値の大きさに関わらず同じ数の有効数字を保持します。指数が小数点位置を決定します。これらの2つの数値を考えてみましょう。
(1) A = 111222333444
(2) B = 0.555666777888
それぞれが12桁の有効数字を持っているため、それぞれがdoubleに収まります。それらの正確な合計は111222333444.555666777888で24桁ですが、doubleは約15桁しか保持できません。A + Bを評価すると、収まらない桁は丸められてしまい、111222333444.55566だけが残ります。
しかし、加算を評価しなければどうなるでしょうか? AとBを並べて保持し、ペアを1つの数値として扱うことに同意すれば、一方が高位の桁を、もう一方が残りの桁を保持します。
double-double値は、2つのdoubleの評価されていない合計を格納します。
(3) x = xhi + xlo
ここで、xhiはxhi + xloがdoubleとして丸められた結果と等しいという不変条件があります。低位部分xloは残りの部分(加算後の高位部分の「誤差」)を保持します。次のセクションのすべての演算はこの不変条件を維持します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
public readonly partial struct DoubleDouble : IEquatable<DoubleDouble>, IComparable<DoubleDouble> {
private readonly double m_hi;
private readonly double m_lo;
/// <summary>
/// 最上位コンポーネント。最近接丸めされたdouble値に等しい。
/// </summary>
public double Hi => m_hi;
/// <summary>
/// 末尾コンポーネント(<see cref="Hi"/>の丸め誤差)。
/// </summary>
public double Lo => m_lo;
}
double-doubleは128ビットですが、これは倍精度浮動小数点数ではありません。IEEE 754(doubleも定義する標準)の128ビット型はbinary128と呼ばれ、一般には倍精度浮動小数点数として知られています。これは113ビットの仮数部と15ビットの指数部(約1e4932まで到達)を持ちます。
double-doubleも128ビットのストレージを使用しますが、これは単に2つの通常のdoubleが隣接しているだけで、合計106ビットの仮数部と、変更されない指数範囲(依然として約1e308でオーバーフロー)になります。1
[画像: 各フォーマットの仮数部のビット数。]図2: 各フォーマットの仮数部のビット数。
3. エラーフリー変換#
すべては1つの観察に基づいています。
double演算で丸めが発生した場合、丸められた量は別のdoubleとして回復できます。
2つのdoubleを加算すると、ハードウェアは真の合計を計算し、それが丸められます。丸められた結果をs = round(a + b)とします。丸められた部分は正確にe = (a + b) - sです。そして、それを取得できれば完了です。なぜならa + b = s + eであり、(s, e)が私たちのdouble-doubleだからです!
しかし、a + bを正確に計算できない場合、eをどのように取得するのでしょうか?このアルゴリズムはKnuthのtwo-sumと呼ばれ、コードリスト2で見ることができます。ビット操作やより広い型を使わずに、6回の加算と減算だけで済みます。
1 2 3 4 5 6 7 8
private static (double Sum, double Error) twoSum(double a, double b) {
double sum = a + b;
double bKept = sum - a; // 合計に含まれたbの部分。
double aKept = sum - bKept; // 合計に含まれたaの部分。
double aLost = a - aKept;
double bLost = b - bKept;
return (sum, aLost + bLost);
}
例の数値AとBでのアルゴリズムは次のとおりです。
1 2 3 4 5 6 7 8 9 10 11 12 13
A = 111222333444
B = 0.555666777888
A + B, exactly = 111222333444.555666777888
sum = A + B = 111222333444.5556640625 <- FPUが返すもの
bKept = sum - A = 0.5556640625
aKept = sum - bKept = 111222333444
aLost = A - aKept = 0
bLost = B - bKept = 0.000002715388
error = aLost + bLost = 0.000002715388
sum + error = 111222333444.555666777888 <- 最後の一桁まで正確
double sumは上位17桁を保持し、残りは予想通り丸められました。しかし、bLostは失われた部分そのものです!オペランドが大きすぎて重ならない極端なケースでは、sumはAまたはBのうち大きい方に丸められ、errorは小さい方になります。
この例ではAは何も失わなかったことに注意してください(aLostは0です)。|a| >= |b|の場合、sumは大きい方のオペランドのすべてのビットを保持するため、aKeptとaLostは関数から完全に省略できます。それがDekkerの高速two-sumです。
1 2 3 4 5
private static (double Sum, double Error) quickTwoSum(double a, double b) {
double sum = a + b;
double bKept = sum - a;
return (sum, b - bKept); // aは何も失わないので、bの損失のみが残る。
}
乗算では、2つの53ビット数の正確な積が必要であり、これは106ビットを必要とします。そのため、高位部分と低位部分に分割します。Dekkerの元の方法(Veltkamp分割)は17回の操作を要しました。ハードウェアにFMA(Fused Multiply-Add)命令があれば、それはわずか2回で済みます。これは、すべての主流プロセッサが持っています。
1 2 3 4 5
private static (double Product, double Error) twoProduct(double a, double b) {
double product = a * b;
double error = Math.FusedMultiplyAdd(a, b, -product);
return (product, error);
}
トリックは、FMAが単一の丸めを最後に行うa*b + cを計算することです。そのため、fma(a, b, -product)として呼び出すことができ、これはa*b - productを評価し、減算がproductが保持したすべてをキャンセルし、最初のa * bが丸められた誤差のみを残します。
これらの3つの関数、twoSum、quickTwoSum、twoProductは、エラーフリー変換と呼ばれ、double-double演算の基礎となります。これらはすべて、最近接丸め演算を仮定し、オーバーフローがないことを前提としています。これらの関数は、無限大やNaNを正しく処理しないことに注意してください。
4. double-double演算のための算術演算の構築#
twoSum、quickTwoSum、twoProductが利用可能になったので、DoubleDoubleの算術演算を記述するのは非常に簡単です。丸めによって桁が失われる可能性のある場所ではエラーフリー変換を使用し、結果が正しく正規化されるようにquickTwoSumで終了することを念頭に置く必要があります。
加算#
1 2 3 4 5 6 7 8 9
public DoubleDouble Add(DoubleDouble right) {
(double sum, double error) = twoSum(m_hi, right.m_hi);
(double lowSum, double lowError) = twoSum(m_lo, right.m_lo);
error += lowSum;
(sum, error) = quickTwoSum(sum, error);
error += lowError;
(sum, error) = quickTwoSum(sum, error);
return new DoubleDouble(sum, error);
}
2つのコンポーネントをペアごとに加算し、次にlowSumとlowErrorを1つずつ組み込みます。lowError自体の加算は丸められる可能性があるため、追加のquickTwoSumが必要です。
11回の操作で済む、より「緩い」バリアントも流通していますが、これは20回の操作を必要とします。これは両方の低位部分m_loとright.m_loを一度に加算します。オペランドが同じ符号を持つ間は問題ありませんが、符号が異なり互いに打ち消し合う場合、相対誤差には上限がなくなります。
乗算#
1 2 3 4 5 6
public DoubleDouble Multiply(DoubleDouble right) {
(double product, double error) = twoProduct(m_hi, right.m_hi);
error += m_hi * right.m_lo + m_lo * right.m_hi + m_lo * right.m_lo;
(product, error) = quickTwoSum(product, error);
return new DoubleDouble(product, error);
}
2つの高位部分をtwoProductで正確に乗算し、次に3つのクロス項を誤差に加算します。クロス項は補正であり、正確である必要はありません。それぞれが補正する積よりも少なくとも2^-53だけ小さいので、通常のdouble演算がそれらから丸め去る量は、積の約2^-106であり、これはペアが保持できる最後のビットです。この丸めのため、乗算は正しく丸められていません。20,000個のランダムなペアに対する正確な積と比較して、約3分の2の確率で最も近い表現可能なペアを返しますが、それ以外の場合は最後のビットから数単位以内です。
平方演算は、3つのクロス項の代わりに2つだけを使用することで最適化できます。また、通常のdoubleとの乗算は1つだけで済みます。これらは、パフォーマンス向上のためのオーバーロードとして持つ価値があります。
除算#
1 2 3 4 5 6 7 8 9 10
public DoubleDouble Divide(DoubleDouble right) {
double quotient1 = m_hi / right.m_hi;
DoubleDouble remainder = Subtract(right.Multiply(quotient1));
double quotient2 = remainder.m_hi / right.m_hi;
remainder = remainder.Subtract(right.Multiply(quotient2));
double quotient3 = remainder.m_hi / right.m_hi;
(double sum, double error) = quickTwoSum(quotient1, quotient2);
return new DoubleDouble(sum, error).Add(FromDouble(quotient3));
}
除算のためのエラーフリー変換はありません。代わりに、商のdouble分を取り、その寄与をdouble-double精度で減算し、長除算を3回繰り返します。
平方根も同様の考え方を使用します。doubleの平方根を取り、次にニュートン法の1回の反復を行います。除算と平方根は、最後の桁で数単位の精度で得られますが、正しく丸められていません(最も近い表現可能なペアではありません)。誤差は、異なる実装に対して最後のビットを再現する必要がある場合にのみ重要になります。
比較#
1 2 3 4
public int CompareTo(DoubleDouble other) {
int hiComparison = m_hi.CompareTo(other.m_hi);
return hiComparison != 0 ? hiComparison : m_lo.CompareTo(other.m_lo);
}
double-doubleの不変条件のおかげで、比較は簡単です。正規化されていないペアが許可される場合、(1, 0.75)と(1.75, 0)は同じ数値であり、異なるものとして比較されることに注意してください。
double-doubleの3つの可能な形状#
これまでは、double-doubleは単に2つのdoubleが密に「貼り合わされた」106個の連続したビットであると想像していたかもしれません。しかし、図3に示すように、必ずしもそうである必要はありません。
[画像: double-doubleペアの3つの可能な形状と、不変条件を破る重複配置。]図3: double-doubleペアの3つの可能な形状と、不変条件を破る重複配置。
- 単一double:
doubleが正確に保持できる値は、lo = 0のペアです。 - 接触:
loはhiの終端から正確に続きます。これにより106個の連続したビットが得られます。例えば、1 + 2^-53は(1, 2^-53)となり、正確です。 - ギャップ: これは興味深いケースで、
loは「さらに下」から始まり、その間のすべてのビット位置は暗黙のゼロです。これは特別なケース、「double-double denormal」のように感じられるかもしれませんが、そうではありません。例のペアは2のギャップを持ちます(コードリスト10)。 - 重複: 存在しません。ウィンドウが重複する場合、
hiはもはやdoubleに丸められた値ではなくなり、不変条件が破られます。例えば、FromTwoDoubles(1.0, 0.75)は正規化され、(1.75, 0)を返します。
例の2のギャップは、ビットをバイナリで書き出すと見ることができます。
1 2 3 4 5 6 7
A = ...0000100. <- 整数ビット37個、最上位は2^36 B = .1000111001000000001011011000... sum = ...0000100.1000111001000000 <- 53ビットウィンドウ、2^-16で終了 error = 001011011000... <- 最初のセットビットは2^-19 ^^ ギャップ: どちらの半分にも格納されていない2つのゼロビット
この場合、error項は偶然2つのゼロで始まります。そのため、ギャップが自然に現れます。それらのゼロは値の実際の桁ですが、doubleは先頭のゼロを格納しません。代わりに、その指数はより低く指します(0.001011と1.011 × 2^-3は同じ数値です)。
ギャップを持つ3番目の形状には1つの注意点があります。余分な精度が「無料」で得られているように見えるかもしれませんが、それは事実です。しかし、ギャップ内のゼロは任意の操作で崩壊する可能性があり、追加の精度が失われる可能性があります。この不条理なケースを考えてみましょう:10^300 + 10^-300は、1,940個のゼロビットのギャップを持つ完全に合法なペアです。しかし、(10^300 + 10^-300) + 1を評価すると、正確な結果は単純に10^300 + 1に崩壊し、10^-300の部分は完全に失われます。
「しかし、10^300をバイナリで書いたときに、たくさんの末尾ゼロはないはずでは?」 その通りです。正確に書くには約700ビットの有効数字が必要です。しかし、例の1e300はその数値ではなく、最も近いdoubleであり、53ビットの仮数部×2のべき乗を格納し、それらの53ビットより下のすべての位置は暗黙的にゼロです。
同じトリックは、2つ以上のdoubleでも機能します。3つでトリプルダブル(約159ビット)、4つでクアドルプルダブル(約212ビット、Hida、Li、BaileyによるQDライブラリ、さらに読む参照)になります。しかし、追加の項ごとに53ビットが追加され、正規化のコストが増大するため、4つ目のdoubleあたりで精度がコストに見合わなくなります。
5. Double-double演算ベンチマーク#
連鎖単一操作レイテンシ、i9-13900K、.NET 10、BenchmarkDotNet:
| 操作 | double | DoubleDouble | 比率 |
|---|---|---|---|
| add | 0.325 ns | 4.07 ns | 12.5x |
| multiply | 0.64 ns | 3.08 ns | 4.8x |
| square | 0.64 ns | 2.83 ns | 4.4x |
| multiply + add | 1.17 ns | 7.08 ns | 6.0x |
| divide | 2.20 ns | 24.09 ns | 10.9x |
加算は高コスト(12.5倍)で、乗算は低コスト(4.8倍)です。これは、FMAのおかげで、私たちが慣れていることとは逆です。そして、除算は両方の型で最も高コストです。
MPFRとの比較#
次に、double-doubleを任意精度ライブラリであるMPFRと比較してみましょう。比較しているコードは、複素平面でznを反復計算するマンデルブロ集合カーネルです。
(4) zn+1 = zn^2 + c
|zn|が永久に有界である場合、cはその集合に属し、ピクセルは黒く塗られます。それが無限大に「脱出」する場合(|z| > 2になると証明されている)、その時点での反復回数が色を決定します。1つの画像は合計約3億9000万回の反復を行います。MPFRは、106ビットの精度で手書きのP/Invokeを通過します。これはdouble-doubleの精度と一致します。
| カーネル | iterations/second | vs double | vs DoubleDouble |
|---|---|---|---|
double | 8,700 M | 1x | |
DoubleDouble | 1,000 M | ~9x | 1x |
| MPFR @106, in place | 108 M | ~81x | ~9x |
| MPFR @106, fresh result per operation | 26 M | ~330x | ~38x |
2つのMPFRスタイルは同じ操作を実行しますが、「fresh result」は値を再利用せず、多くのラッパーが提示する方法で操作ごとに割り当てを行います。
ご覧のとおり、double-doubleはdoubleの約9倍のコストがかかり、MPFRはdouble-doubleのさらに約9倍のコストがかかります。3
「fresh result」行の減速は回避可能ですが、値を正しく再利用する規律を維持するのはコード作成者の責任です(例:各操作が新しい値を割り当てるため、式としてa * b + cと書かない)。DoubleDoubleはヒープ割り当てを行わないため、zRe * zIm * 2.0 + cImのように通常どおり記述でき、何も割り当てません。
9倍という数字は私の特定のケースのものであり、反復ごとに7回の算術演算から来ています。したがって、double-doubleの使用経験は異なる場合があります。
任意精度浮動小数点数と比較して、DoubleDoubleにはいくつかの利点があります。
- double-doubleの加算または乗算はわずか7〜20命令であり、多くの場合インライン化されます。これは、MPFRとは異なり、関数呼び出し(.NETではさらにP/Invoke境界がある)です。
- 命令シーケンスは固定されており、分岐がないため、CPUパイプラインに優しいです。MPFRのような配列に対するデータ依存ループとは異なります。
- ベクトル化および移植が可能です。
Vector256<double>を使用してdouble-double演算を書き直すことが可能で、一度に4つの値を処理します。同じ算術演算がGPUにもポートされます。これはコンパイラ/JITが自動で行うのではなく書き直しですが、任意精度ライブラリではこのような書き直しは不可能でしょう。
__float128との比較#
GCC/ClangでC/C++を書いている場合、倍精度__float128が組み込まれており、すべての算術演算が利用可能です。ただし、x86または主流のARMプロセッサはハードウェアで__float128を実装していないため、コンパイラはすべての操作をエミュレートします。同じ連鎖ループとカーネルを使用して測定した結果(今回はC言語4):
| カーネル (C, シングルコア) | iterations/second | vs double | vs DoubleDouble |
|---|---|---|---|
double | 531 M | 1x | |
long double (x87) | 441 M | 1.2x | |
DoubleDouble | 76 M | ~7x | 1x |
__float128 | 12.4 M | ~43x | ~6x |
操作あたり、__float128はdouble-doubleよりも2〜4倍遅いですが(連鎖ループ、未表示)、マンデルブロカーネル全体では6倍遅くなります。long double行は、64ビットの仮数部を持つFPUアクセラレーテッド型を追加データポイントとして示しています。
__float128の6倍の遅延は、7ビットの精度向上、はるかに広い指数範囲、正しい丸め、および正常に機能する無限大/NaNといった利点をもたらします。__float128がハードウェアでアクセラレートされているプラットフォーム(例:IBM POWER9以降)では、それを使用してください!x86では価値がありません。.NETでは、残念ながら128ビット浮動小数点型が存在しないため、この問題は発生しません。
6. ショーケース: 深いマンデルブロ集合のズーム#
この作業のきっかけとなったマンデルブロ集合のレンダリングを見てみましょう。レンダラーが描画しようとしているのは次のとおりです。
1 2 3 4 5
private const string CENTER_RE = "-0.74364389112485980556186";
private const string CENTER_IM = "0.13182591316154390843318";
private const double MARQUEE_WIDTH = 7.746e-15;
private const double ESCAPE_SQUARED = 65536.0 * 65536.0;
コードリスト12は、C#でのdouble-doubleカーネルを示しており、残りはAppendix B: the benchmarked kernelsにあります。
1 2 3 4 5 6 7 8 9 10 11 12 13
DoubleDouble zRe = DoubleDouble.Zero;
DoubleDouble zIm = DoubleDouble.Zero;
for (; n < maxIterations; n++) {
DoubleDouble zReSquared = zRe.Square();
DoubleDouble zImSquared = zIm.Square();
magnitudeSquared = zReSquared.Hi + zImSquared.Hi;
if (magnitudeSquared > ESCAPE_SQUARED) {
break;
}
zIm = zRe * zIm * 2.0 + cIm;
zRe = zReSquared - zImSquared + cRe;
}
[画像: 1e-3幅のビュー。この深さでは、両方のタイプが同じ画像をレンダリングします。]図4: 1e-3幅のビュー。この深さでは、両方のタイプが同じ画像をレンダリングします。
-
double
-
double-double
図5: 7.7e-15のビュー。doubleレンダリングはブロックに量子化されますが、double-doubleレンダリングは影響を受けません。
ここでのピクセルステップは約1.5e-17で、隣接するdouble間のギャップの7分の1です。そのため、ブロックは約7ピクセル幅になり、さらにズームするたびに広がり、フレーム全体が1つのブロックになります。double-doubleではブロックがなくなり、約1e-28の幅まで詳細が保持されます。
しかし、さらに進むと、同じことがdouble-doubleにも起こります。図6がそれを示しています。
-
double-double
-
比較用摂動
図6: 4.9e-31幅の近くの中心、16桁深い場所。double-doubleレンダリングもブロックに量子化されます。右側の参照は真の値です。
7. ジュリア集合の問題#
これまでは、点の表現の細かさだけを測定しました。しかし、計算に残る精度は別の問題であり、ジュリア集合はそれを私に非常に明確にしました。
ジュリア集合は(方程式4)を再度使用しますが、2つの役割が入れ替わっています。cは画像全体で1つの定数であり、ピクセル座標はゼロの代わりに開始z0です。したがって、演算と反復あたりのコストは同じですが、画像は予想よりも早く崩壊します。
私は自分のレンダラーでジュリア集合をブラウズしているときにこれに遭遇しました。画像の中央(原点)に最も興味深い構造があることがよくあったため、そこにズームインしました。グリッチは非常に早く現れたため、最初はコードにバグがあると思いました。また、見た目も非常に異なっていました。しかし、カーネルをdouble-doubleに切り替えることでそれらは完全に解消されたため、バグはコードにはなく、何がなくなったのかを探し始めました。
-
double
-
double-double
図7: 約3e-7幅のジュリア集合ビュー。この記事の冒頭のマンデルブロ集合は、7桁以上深く、きれいに表示されます。
ここでの問題は、前述の例のようなdoubleの「密度」ではありません。精度はループの最初の反復で失われます。平方するとピクセルの座標は小さくなりますが、doubleは重要な桁をすべて保持します。次のステップで、その小さな平方された結果が約0.75の数値cに加えられるときに桁が失われます。例を挙げます。
1 2 3 4 5 6 7 8 9 10 11 12 13
z_0 = 0.000000012 ピクセル z_0^2 = 0.000000000000000144 正確、doubleの全16桁まで c = 0.75 c + z_0^2 = 0.750000000000000144 合計が本来あるべき姿 c + z_0^2 = 0.750000000000000111 最も近いdouble、23%不足 ^^^ 次のピクセル、3.1e-10離れている: z_0 = 0.0000000123125 異なる座標 z_0^2 = 0.000000000000000152 そして異なる平方 c + z_0^2 = 0.750000000000000111 全く同じdoubleに丸められる
例からわかるように、3.1e-10離れて開始した2つのピクセルは、2回目の反復が始まる前に区別がつかなくなります。図7のジュリア集合の原点付近の近傍では、すべてのピクセルが同じz1 = cに収束し、大きな灰色の領域として示されています。その隣のdouble-doubleは、そこに螺旋を描画します。
また、グリッチの見た目が異なることにも注意してください。軸に沿ったブロックではなく、システムの反復ダイナミクスによって増幅された丸め誤差から生じるギザギザの裂け目が見えます。
ジュリア集合の原点の周りでは、使用可能なズームは、同じ型がマンデルブロ集合で管理できるズームの平方根、つまり半分の桁数です。しかし、原点から離れるにつれて、グリッチは消えます。
8. 実単位でのズーム深度#
double-doubleは、10^29の範囲のズームでレンダリングします。これらの数値は感覚を掴むのが難しいので、いくつかの面白い事実を挙げます。
マンデルブロ集合全体をスマートフォンの画面(幅約7cm、約1200ピクセル)に表示するとします。次に、ピンチインして、隣接するピクセルが同じ座標に丸められるようになるまでズームを続けます(図5のようになります)。そして、その時点までにセット全体がどれだけ大きくなったかを尋ねます。
ピンチ操作ごとにズームが2倍になり、1秒かかるとします。double精度では、44秒後に完了し、画面は1.3e-13単位の幅になります。そのスケールで描画されたセット全体は、12億kmの幅になり、地球から太陽までの距離の8倍、ここから木星を通り過ぎるまで達します。
DoubleDoubleでは、さらに53秒間ピンチを続け、幅1.5e-29までズームします。元のセットは12個の観測可能な宇宙の幅になります!
そして、さらにずっと深く進みます!図8は、22分間続いた同じピンチ操作を示しており、幅2.5e-398のビューになります。これは、中心を400桁以上の十進数で表現する必要があります。doubleは15桁、double-doubleは31桁です。
[画像: 幅2.5e-398のビュー、セット全体から1,322倍の深さ、摂動によって計算。中心を配置するには約400桁の十進数が必要です。doubleは15桁、double-doubleは31桁です。]図8: 幅2.5e-398のビュー、セット全体から1,322倍の深さ、摂動によって計算。中心を配置するには約400桁の十進数が必要です。doubleは15桁、double-doubleは31桁です。5
9. double-doubleの限界#
double-doubleには以下の限界があります。
- 表現可能な範囲は変更されず、使用可能な範囲はわずかに狭くなります。オーバーフローは依然として1e308ですが、完全な精度は通常2e-292までしか持続しません。それ以下では、低位コンポーネントがサブノーマルになり、正確な積は正確でなくなり、ペアは通常のdoubleに劣化します。
- 無限大は正しくサポートされていません。誤差項は
inf - infを計算するため、最初のオーバーフローまたはゼロ除算は、doubleが無限大を生成するのに対し、NaNを返します。マンデルブロ集合カーネルは、何かがそれほど大きくなる前に反復を停止するため、安全です。 - 比較は2つの部分に対する辞書順比較です。そのため、NaNはすべての実数値より小さくソートされます(通常のdoubleでは、NaNとの比較はすべて偽になります)。また、
EqualsとCompareToは2つのNaNが同じかどうかについて意見が一致しません。 - 操作は正しく丸められていません。保証は相対誤差(例:積で
2^-106)に関するものです。正しい丸めがないと、式の並べ替え(例:結合法則を使用)は、通常のdoubleの場合よりも結果をより多く変更します。これはテストを複雑にする可能性があります。 - コンパイラが「助けて」はなりません。すべてのエラーフリー変換は、操作が正確に記述されたとおりに、正確にdouble精度で行われることに依存しています。例えば、
-ffast-mathを使用したCおよびC++は、sum - aを再結合して削除します。幸いなことに、.NET(RyuJIT)は浮動小数点式の最適化を一切行っていません。
10. 結論#
この記事で議論されたすべてのフォーマットを以下に示します。
| フォーマット | 十進桁数 | doubleに対するパフォーマンス | 長所 | 短所 |
|---|---|---|---|---|
float | ~7 | ~1x | メモリ半分、SIMDレーン2倍 | 低精度 |
double | ~15 | 1x | 高速、高精度 | 精度が足りなくなる可能性 |
long double (x87) | ~19 | ~1.2x | 追加精度が無料 | x86およびGCC/Clangのみ、SIMDなし、4桁のみ追加 |
DoubleDouble | ~31 | ~9x | ヒープなし、依存関係なし、インライン化、ベクトル化可能 | 無限大が壊れる、正しく丸められない、自分で管理する約200行 |
__float128 | ~34 | ~40x | 高精度と1e4932までの範囲 | x86ではソフトウェアエミュレーション、限定的なサポート |
| MPFR | 要求するだけ | ~80x以上 | 無制限の精度 | 値ごとのヒープ、P/Invoke、割り当て規律が必要 |
double-doubleがMPFRよりも高速であることは知っていましたが、ちょうど中間にあることに驚きました。私がこの型を最初に書いたのは、MPFRに対する速度向上のためでした。これにより、私のエクスプローラーは拡張ズームレベルでもインタラクティブに保たれ、高解像度レンダリングが実用的になりました。
double-doubleは非常にニッチな型ですが、それでも、それが有用であると確信できたことを願っています。例えば、GPUやWebブラウザのような任意精度ライブラリにアクセスできない環境でコードを実行する必要がある場合、または単に少し高い精度が必要でパフォーマンスが重要な場合です。
最後に、深いマンデルブロ集合のズームに関しては、総当たり的な精度が最先端ではないことに言及すべきです。摂動理論は、すべての計算に任意精度を使用せずに非常に深いズームを可能にしますが、それについてはいつか別の機会に。double-doubleの便利な使い方を知っている場合、またはそれを使用することになった場合は、お知らせください!
[画像: そして最後に少し追加。幅3.9e-811のビュー、セット全体から2,693倍の深さ、摂動によって計算。そしてまだ底には達していません!]図9: そして最後に少し追加。幅3.9e-811のビュー、セット全体から2,693倍の深さ、摂動によって計算。そしてまだ底には達していません!
11. さらに読む#
- T. J. Dekker, "A Floating-Point Technique for Extending the Available Precision", Numerische Mathematik, 1971. 元の論文。分割トリックと高速two-sumの両方がここから来ています。
- D. E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, section 4.2.2. 6回の操作の
twoSumと、それが正確であることの証明。 - Y. Hida, X. S. Li and D. H. Bailey, "Algorithms for Quad-Double Precision Floating Point Arithmetic", 2001. QDライブラリの背後にある論文、標準的なdouble-doubleおよびquad-double実装。
- M. Joldes, J.-M. Muller and V. Popescu, "Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic", ACM TOMS, 2017. ここで使用されている加算、乗算、除算の基本的な構成要素の厳密な誤差境界。
- J. R. Shewchuk, "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates", 1997. 入力に応じて精度が適応するn個のdoubleの展開に手法を拡張します。
フットノート
- 命名はC言語の
long doubleでさらに混乱します。その意味はプラットフォームとコンパイラに依存します。IBM POWERでは実際にはdouble-doubleです(GCCはそれを__ibm128と呼び、__float128をIEEE型用に予約しています)。x86ではさらに別の型です:GCCとClangは64ビット仮数部を持つ80ビットx87拡張フォーマットを提供しますが、MSVCはそれをdoubleの別の名前として扱います。↩ - 表示されている数値は読みやすさのために丸められています。十進数形式の数値には、十進数から二進数への変換による追加の桁が含まれますが、アルゴリズムはそれらをすべて正確に処理します。↩
- アイドル状態のマシンで3回の実行の中央値を取り、実行間のばらつきは数パーセントです。結果の反復回数はすべての実行で同じでした。↩
- gcc 14.2、
-O2、FMA縮小オフ、同じi9-13900KのPコア1つ。double-doubleはAppendix Aの行ごとのC言語ポートであり、.NETの操作あたりの数値を数パーセント以内で再現します。↩ - 以前にこの場所を見た人はいませんでした。座標が書き留められていないと、私自身も含め、誰もそれを見つけることができませんでした。それは、観測可能な宇宙全体から特定の砂粒を1つ探すようなものです。たとえ正しい惑星を見つけたとしても、探索は絶望的でしょう。したがって、正確な座標(それぞれ406桁)を以下に示します。実部:
-1.2546501186909057505269466250921981644070768100251708177516070303734046805262190991942188750230768678605788326475221138767425434553956510745751843244663895032007841539877137705604003669583875944006181706618704710525415050302476211752688927355924699367031357139525690997877831869648195623522823691538908055742989329820011761064778120010166893341652782500699958380682058425509820660627053365326418384253599781. 虚部:0.3819035642800001819461581237720802452234485990147800334446378567314132368999769468860848762828896508632064176850184911749715609976648123007802564910929725517436736759042462717235720004499322510654559848620036722449528324306932522044048459018966997955517496317108858725278768456014781914592217389991723653848006887239802789886568674879888329442270299742538205772252794459812326617996073246041743419429748869. ビューポートは高さ1.906e-398です。↩
付録A: 型全体#
型全体は2つのファイルにあります。最初のファイルには算術演算が含まれており、Systemのみに依存しています。これは、数学だけが必要な場合にコピーする部分です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
// 約200行のDouble-double演算。このファイルはSystemのみに依存するため、
// どのプロジェクトにもコピーできます。印刷と解析はBigIntegerを使用し、
// DoubleDoubleFormat.csにあります。
namespace DoubleDoubleSample;
/// <summary>
/// 2つのdoubleの評価されていない合計として格納される値: 約106ビットの仮数部
/// (~31十進桁) を、doubleの数倍のコストで、ヒープ割り当てなしで実現します。
///
/// 不変条件: Hi == RoundToNearest(Hi + Lo)、つまり |Lo| は Hi の半Ulp以下です。
/// 以下のすべてのファクトリと操作はこれを維持します。比較とToDoubleはこれに依存します。
///
/// 操作は正しく丸められていませんが、正確な結果の2^-106の数単位内に収まります。
/// 指数範囲は通常のdoubleと同じであり、無限大は特別扱いされません。
/// 無限大に対する最初の操作はNaNを返します(誤差項はinf - infを計算します)。
///
/// Marek Fiser著、marekfiser.com/blog/double-double-arithmetic/ (CC BY 4.0) より。
/// </summary>
public readonly partial struct DoubleDouble : IEquatable<DoubleDouble>, IComparable<DoubleDouble> {
private readonly double m_hi;
private readonly double m_lo;
/// <summary>最上位コンポーネント。最近接丸めされたdouble値に等しい。</summary>
public double Hi => m_hi;
/// <summary>末尾コンポーネント(<see cref="Hi"/>の丸め誤差)。</summary>
public double Lo => m_lo;
public bool IsZero => m_hi == 0.0;
/// <summary>-1、0、または+1(NaNの場合は0)。</summary>
public int Sign => m_hi > 0.0 ? 1 : m_hi < 0.0 ? -1 : 0;
public static DoubleDouble Zero { get; } = new DoubleDouble(0.0, 0.0);
public static DoubleDouble One { get; } = new DoubleDouble(1.0, 0.0);
private DoubleDouble(double hi, double lo) {
m_hi = hi;
m_lo = lo;
}
/// <summary>doubleからの正確な変換。</summary>
public static DoubleDouble FromDouble(double value) {
return new DoubleDouble(value, 0.0);
}
/// <summary>2つの任意のdoubleの正確な合計 <paramref name="hi"/> + <paramref name="lo"/>。</summary>
public static DoubleDouble FromTwoDoubles(double hi, double lo) {
// 不変条件が満たされるように正規化します。
(double sum, double error) = twoSum(hi, lo);
return new DoubleDouble(sum, error);
}
public DoubleDouble Add(DoubleDouble right) {
// 2つのコンポーネントをペアごとに加算し、次にlowSumとlowErrorを1つずつ組み込みます。
// lowErrorの加算は丸められる可能性があるため、2回目のquickTwoSumで結果を正規化します。
(double sum, double error) = twoSum(m_hi, right.m_hi);
(double lowSum, double lowError) = twoSum(m_lo, right.m_lo);
error += lowSum;
(sum, error) = quickTwoSum(sum, error);
error += lowError;
(sum, error) = quickTwoSum(sum, error);
return new DoubleDouble(sum, error);
}
public DoubleDouble Subtract(DoubleDouble right) {
return Add(right.Negate());
}
public DoubleDouble Multiply(DoubleDouble right) {
// hi*hiを正確に、次に3つのクロス項。
// 各クロス項は積より少なくとも2^-53小さいため、通常のdouble演算で十分です。
(double product, double error) = twoProduct(m_hi, right.m_hi);
error += m_hi * right.m_lo + m_lo * right.m_hi + m_lo * right.m_lo;
(product, error) = quickTwoSum(product, error);
return new DoubleDouble(product, error);
}
/// <summary>通常のdoubleとの乗算。完全なdouble-double積よりも高速です。</summary>
public DoubleDouble Multiply(double right) {
(double product, double error) = twoProduct(m_hi, right);
error += m_lo * right;
(product, error) = quickTwoSum(product, error);
return new DoubleDouble(product, error);
}
/// <summary>他の操作よりも遅く、わずかに精度が低い。</summary>
public DoubleDouble Divide(DoubleDouble right) {
// 長除算の3ステップ。
double quotient1 = m_hi / right.m_hi;
DoubleDouble remainder = Subtract(right.Multiply(quotient1));
double quotient2 = remainder.m_hi / right.m_hi;
remainder = remainder.Subtract(right.Multiply(quotient2));
double quotient3 = remainder.m_hi / right.m_hi;
(double sum, double error) = quickTwoSum(quotient1, quotient2);
return new DoubleDouble(sum, error).Add(FromDouble(quotient3));
}
/// <summary>一般的な積よりもわずかに高速です。</summary>
public DoubleDouble Square() {
(double product, double error) = twoProduct(m_hi, m_hi);
error += 2.0 * m_hi * m_lo + m_lo * m_lo;
(product, error) = quickTwoSum(product, error);
return new DoubleDouble(product, error);
}
public DoubleDouble Negate() {
// 否定は丸められないため、これは正確です。
return new DoubleDouble(-m_hi, -m_lo);
}
public DoubleDouble Abs() {
return Sign < 0 ? Negate() : this;
}
/// <summary>他の操作よりもわずかに精度が低い。負の数やNaN入力は
/// NaNを返します。Math.Sqrtと同様です。</summary>
public DoubleDouble Sqrt() {
if (!(m_hi > 0.0)) { // "m_hi <= 0.0"ではない。この形式はNaNにも真であるため。
return FromDouble(Math.Sqrt(m_hi));
}
// doubleの平方根からの1回のニュートンステップ。
double approx = Math.Sqrt(m_hi);
DoubleDouble residual = Subtract(FromDouble(approx).Square());
double correction = residual.m_hi / (approx + approx);
(double hi, double lo) = quickTwoSum(approx, correction);
return new DoubleDouble(hi, lo);
}
public double ToDouble() {
return m_hi;
}
public int CompareTo(DoubleDouble other) {
// 正規化されたペアに対してのみ正確です。
int hiComparison = m_hi.CompareTo(other.m_hi);
return hiComparison != 0 ? hiComparison : m_lo.CompareTo(other.m_lo);
}
public bool Equals(DoubleDouble other) {
return m_hi == other.m_hi && m_lo == other.m_lo;
}
public override bool Equals(object? obj) {
return obj is DoubleDouble other && Equals(other);
}
public override int GetHashCode() {
return HashCode.Combine(m_hi, m_lo);
}
public static DoubleDouble operator +(DoubleDouble left, DoubleDouble right) => left.Add(right);
public static DoubleDouble operator -(DoubleDouble left, DoubleDouble right) => left.Subtract(right);
public static DoubleDouble operator *(DoubleDouble left, DoubleDouble right) => left.Multiply(right);
public static DoubleDouble operator *(DoubleDouble left, double right) => left.Multiply(right);
public static DoubleDouble operator /(DoubleDouble left, DoubleDouble right) => left.Divide(right);
public static DoubleDouble operator -(DoubleDouble value) => value.Negate();
public static bool operator ==(DoubleDouble left, DoubleDouble right) => left.Equals(right);
public static bool operator !=(DoubleDouble left, DoubleDouble right) => !left.Equals(right);
public static bool operator <(DoubleDouble left, DoubleDouble right) => left.CompareTo(right) < 0;
public static bool operator >(DoubleDouble left, DoubleDouble right) => left.CompareTo(right) > 0;
public static bool operator <=(DoubleDouble left, DoubleDouble right) => left.CompareTo(right) <= 0;
public static bool operator >=(DoubleDouble left, DoubleDouble right) => left.CompareTo(right) >= 0;
// doubleからの変換は正確なので、暗黙的です。doubleへの変換は
// 低位コンポーネントをドロップするため、明示的です。
public static implicit operator DoubleDouble(double value) => FromDouble(value);
public static explicit operator double(DoubleDouble value) => value.ToDouble();
/// <summary>Knuthのtwo-sum: sum + error == a + b を正確に、任意の2つのdoubleに対して。</summary>
private static (double Sum, double Error) twoSum(double a, double b) {
// 浮動小数点加算の丸め誤差は、それ自体がdoubleとして表現可能です。
// 中間結果は丸められる可能性がありますが、それらの丸め誤差は相殺されます。
double sum = a + b;
double bKept = sum - a; // 合計に含まれたbの部分。
double aKept = sum - bKept; // 合計に含まれたaの部分。
double aLost = a - aKept;
double bLost = b - bKept;
return (sum, aLost + bLost);
}
/// <summary>Dekkerの高速two-sum: twoSumと同じ保証、|a| >= |b| (またはa == 0) の場合にのみ有効。</summary>
private static (double Sum, double Error) quickTwoSum(double a, double b) {
double sum = a + b;
double bKept = sum - a;
return (sum, b - bKept); // aは何も失わないので、bの損失のみが残る。
}
/// <summary>正確な積: product + error == a * b を正確に、積が正規のdoubleである限り。
/// 約2e-292以下では、誤差はdoubleに収まらなくなります。</summary>
private static (double Product, double Error) twoProduct(double a, double b) {
// 融合積和演算は、単一の丸めでa*b - productを計算します。これは
// 106ビット積の下位半分です。FMA命令を持たないCPUでは、
// Math.FusedMultiplyAddはソフトウェアで同じ結果を計算しますが、はるかに遅いです。
double product = a * b;
double error = Math.FusedMultiplyAdd(a, b, -product);
return (product, error);
}
}
2番目のファイルには、BigIntegerを使用した正確な印刷と解析が含まれています(BCLの一部であるため、NuGet依存関係はありません)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
// DoubleDoubleの印刷と解析。ToString()はデフォルトで36桁の有効数字を印刷します。
// これは、コンポーネントが連続している値のいずれかをラウンドトリップするのに十分です。
// BigIntegerを使用して正確な有理数に変換し、それから丸められた十進数に変換します。
using System.Globalization;
using System.Numerics;
using System.Text;
namespace DoubleDoubleSample;
public readonly partial struct DoubleDouble {
/// <summary>ToString()が印刷する有効数字の数: コンポーネントが連続している
/// 値のいずれかをラウンドトリップするのに十分です(<see cref="Parse"/>を参照)。</summary>
private const int DEFAULT_DIGITS = 36;
/// <summary>デフォルトの36桁でフォーマットします。</summary>
public override string ToString() {
return ToString(DEFAULT_DIGITS);
}
/// <summary>指定された数の有効な十進桁数でフォーマットし、正確に丸めます。</summary>
public string ToString(int significantDigits) {
if (significantDigits < 1) {
throw new ArgumentOutOfRangeException(nameof(significantDigits));
}
if (!double.IsFinite(m_hi)) {
return m_hi.ToString(CultureInfo.InvariantCulture);
}
(BigInteger numerator, BigInteger denominator) = toRational(this);
return formatRational(numerator, denominator, significantDigits);
}
/// <summary>
/// 正確な値をフォーマットします。double-doubleは2つの二進数小数点の合計であるため、
/// 常に有限の十進数展開を持ちますが、コンポーネントが離れている場合は数百桁になることがあります。
/// </summary>
public string ToStringExact() {
if (!double.IsFinite(m_hi)) {
return m_hi.ToString(CultureInfo.InvariantCulture);
}
(BigInteger numerator, BigInteger denominator) = toRational(this);
if (numerator.IsZero) {
return "0";
}
// 分母は2のべき乗なので、対応する5のべき乗を掛けると
// 10のべき乗になり、十進数の桁が直接得られます。
int twos = (int)(denominator.GetBitLength() - 1);
BigInteger scaled = BigInteger.Abs(numerator) * BigInteger.Pow(5, twos);
string digits = scaled.ToString(CultureInfo.InvariantCulture).PadLeft(twos + 1, '0');
string sign = numerator.Sign < 0 ? "-" : "";
if (twos == 0) {
return sign + digits;
}
string result = sign + digits[..^twos] + "." + digits[^twos..];
return result.TrimEnd('0').TrimEnd('.');
}
/// <summary>
/// 最近接のdouble-doubleに十進文字列を解析します。値は正確な有理数として構築され、
/// 各コンポーネントに1回丸められます。コンポーネントが連続している値については、
/// <see cref="ToString()"/>とのラウンドトリップが可能です。手動で構築されたペア(例:(1.0, 1e-300))は、
/// 36桁では表現できない情報を持っています。
/// </summary>
public static DoubleDouble Parse(string text) {
(BigInteger numerator, BigInteger denominator) = parseRational(text);
double hi = toNearestDouble(numerator, denominator);
if (!double.IsFinite(hi)) {
return FromDouble(hi);
}
// 先頭コンポーネントを正確に減算し、残りを末尾コンポーネントに丸めます。
(BigInteger hiNumerator, BigInteger hiDenominator) = toRational(FromDouble(hi));
BigInteger restNumerator = numerator * hiDenominator - hiNumerator * denominator;
BigInteger restDenominator = denominator * hiDenominator;
double lo = toNearestDouble(restNumerator, restDenominator);
return FromTwoDoubles(hi, lo);
}
/// <summary>double-doubleの正確な値(分母は2のべき乗)。</summary>
private static (BigInteger Numerator, BigInteger Denominator) toRational(DoubleDouble value) {
(BigInteger hiNumerator, BigInteger hiDenominator) = toRational(value.m_hi);
(BigInteger loNumerator, BigInteger loDenominator) = toRational(value.m_lo);
return (hiNumerator * loDenominator + loNumerator * hiDenominator, hiDenominator * loDenominator);
}
/// <summary>有限なdoubleの正確な値(ビットから)。</summary>
private static (BigInteger Numerator, BigInteger Denominator) toRational(double value) {
long bits = BitConverter.DoubleToInt64Bits(value);
int exponent = (int)((bits >> 52) & 0x7FF);
long mantissa = bits & 0xF_FFFF_FFFF_FFFFL;
if (exponent == 0) {
exponent = -1074; // サブノーマル: 暗黙の先頭ビットなし
} else {
mantissa |= 1L << 52;
exponent -= 1075;
}
BigInteger numerator = bits < 0 ? -mantissa : mantissa;
return exponent >= 0
? (numerator << exponent, BigInteger.One)
: (numerator, BigInteger.One << -exponent);
}
/// <summary>正確な有理数を最近接のdoubleに丸めます(タイは偶数に丸めます)。</summary>
private static double toNearestDouble(BigInteger numerator, BigInteger denominator) {
if (numerator.IsZero) {
return 0.0;
}
int sign = numerator.Sign;
numerator = BigInteger.Abs(numerator);
// 商が[2^52, 2^54)の範囲になるようにスケールします。
// その後、1回の整数除算で仮数部のすべてのビットと丸めに必要な残りが得られます。
long exponent = numerator.GetBitLength() - denominator.GetBitLength() - 53;
if (exponent > 0) {
denominator <<= (int)exponent;
} else {
numerator <<= (int)-exponent;
}
BigInteger quotient = BigInteger.DivRem(numerator, denominator, out BigInteger remainder);
if (quotient.GetBitLength() > 53) {
// ビットが1つ多すぎます。それを指数に移動し、丸め決定を正確に保つために
// 残りにドロップされたビットを追加します。
if (!quotient.IsEven) {
remainder += denominator;
}
quotient >>= 1;
denominator <<= 1;
exponent++;
}
int comparison = (remainder << 1).CompareTo(denominator);
if (comparison > 0 || (comparison == 0 && !quotient.IsEven)) {
quotient++;
if (quotient.GetBitLength() > 53) {
quotient >>= 1;
exponent++;
}
}
return sign * Math.ScaleB((double)quotient, (int)exponent);
}
/// <summary>十進文字列(例: "-1.25e-7")を正確な有理数に解析します。</summary>
private static (BigInteger Numerator, BigInteger Denominator) parseRational(string text) {
text = text.Trim();
if (text.Length == 0) {
throw new FormatException("空の入力です。");
}
int index = 0;
bool negative = text[index] == '-';
if (negative || text[index] == '+') {
index++;
}
BigInteger mantissa = BigInteger.Zero;
int fractionDigits = 0;
bool seenDot = false;
bool seenDigit = false;
for (; index < text.Length; index++) {
char c = text[index];
if (c == '.') {
if (seenDot) {
throw new FormatException($"'{text}'内に2つの小数点があります。");
}
seenDot = true;
} else if (c is >= '0' and <= '9') {
mantissa = mantissa * 10 + (c - '0');
seenDigit = true;
if (seenDot) {
fractionDigits++;
}
} else if (c is 'e' or 'E') {
break;
} else {
throw new FormatException($"'{text}'内に予期しない文字 '{c}' があります。");
}
}
if (!seenDigit) {
throw new FormatException($"'{text}'に数字がありません。");
}
int exponent = -fractionDigits;
if (index < text.Length) {
exponent += int.Parse(text[(index + 1)..], CultureInfo.InvariantCulture);
}
if (negative) {
mantissa = -mantissa;
}
return exponent >= 0
? (mantissa * BigInteger.Pow(10, exponent), BigInteger.One)
: (mantissa, BigInteger.Pow(10, -exponent));
}
/// <summary>正確な有理数をN桁の有効数字に丸め、フォーマットします。</summary>
private static string formatRational(BigInteger numerator, BigInteger denominator, int digits) {
if (numerator.IsZero) {
return "0";
}
bool negative = numerator.Sign < 0;
numerator = BigInteger.Abs(numerator);
// ビット長から十進数の指数を推定します(log10(2) ~ 0.30103)。
// 下のループで、推定値が1ずれている場合に補正します。
int exponent10 = (int)Math.Floor((numerator.GetBitLength() - denominator.GetBitLength()) * 0.30103);
string text;
while (true) {
int scale = digits - 1 - exponent10;
BigInteger scaledNumerator = numerator;
BigInteger scaledDenominator = denominator;
if (scale >= 0) {
scaledNumerator *= BigInteger.Pow(10, scale);
} else {
scaledDenominator *= BigInteger.Pow(10, -scale);
}
BigInteger rounded = roundToNearest(scaledNumerator, scaledDenominator);
text = rounded.ToString(CultureInfo.InvariantCulture);
if (text.Length == digits) {
break;
}
// 1ずれている(推定値が低すぎる、または丸めによって新しい桁に繰り上がった)。
exponent10 += text.Length - digits;
}
text = text.TrimEnd('0');
if (text.Length == 0) {
text = "0";
}
StringBuilder result = new(negative ? "-" : "");
if (exponent10 >= -5 && exponent10 < digits) {
// 読みやすい範囲では位置記数法を使用します。
if (exponent10 >= 0) {
text = text.PadRight(exponent10 + 1, '0');
result.Append(text[..(exponent10 + 1)]);
if (text.Length > exponent10 + 1) {
result.Append('.').Append(text[(exponent10 + 1)..]);
}
} else {
result.Append("0.").Append('0', -exponent10 - 1).Append(text);
}
} else {
result.Append(text[0]);
if (text.Length > 1) {
result.Append('.').Append(text[1..]);
}
result.Append('e').Append(exponent10.ToString(CultureInfo.InvariantCulture));
}
return result.ToString();
}
/// <summary>整数(numerator/denominator)、タイはゼロから離れる方向に丸めます(両方とも正)。</summary>
private static BigInteger roundToNearest(BigInteger numerator, BigInteger denominator) {
BigInteger quotient = BigInteger.DivRem(numerator, denominator, out BigInteger remainder);
return (remainder << 1) >= denominator ? quotient + 1 : quotient;
}
}
付録B: ベンチマークされたカーネル#
セクション5: Double-double演算ベンチマークの数値は、これらのベンチマークから得られたものです。ピクセルループとスレッディングは3つのカーネルすべてで同じであり、表示されていません。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
namespace DoubleDoubleSample.Mandelbrot;
/// <summary>
/// 3つのバージョン(double、DoubleDouble、およびMPFR)のマンデルブロ集合エスケープ時間カーネル。
/// さらに、MPFRバージョンが必要とする一時変数のセット。
/// ピクセルの中心の解析、行の分割、およびタイミングはMandelbrotRenderer.csにあります。
///
/// 3つすべてが反復ごとに同じ7つの操作を実行し、各ピクセルに対して同じ反復回数をカウントします。
/// 各カーネルは、その型にとって最も安価なエスケープテストを使用します。
/// 操作ごとに新しい値を割り当てる4番目のバリアント(ラッパーが通常行う方法)もMandelbrotRenderer.csにあります。
/// </summary>
public static unsafe partial class MandelbrotRenderer {
/// <summary>脱出半径の2乗。スムージング反復公式が正確になるように、大きく設定。</summary>
private const double ESCAPE_SQUARED = 65536.0 * 65536.0;
/// <summary>参照用の通常のdouble。</summary>
private static double iterateDouble(
double cRe,
double cIm,
int maxIterations,
out int iterations
) {
double zRe = 0.0;
double zIm = 0.0;
double magnitudeSquared = 0.0;
int n = 0;
for (; n < maxIterations; n++) {
double zReSquared = zRe * zRe;
double zImSquared = zIm * zIm;
magnitudeSquared = zReSquared + zImSquared;
if (magnitudeSquared > ESCAPE_SQUARED) {
break;
}
zIm = 2.0 * zRe * zIm + cIm;
zRe = zReSquared - zImSquared + cRe;
}
iterations = n;
return magnitudeSquared;
}
/// <summary>
/// `double`の代わりに`<c>DoubleDouble</c>`を代入した同じコード。エスケープテストは
/// 最上位コンポーネントを直接読み取ります。
/// </summary>
private static double iterateDoubleDouble(
DoubleDouble cRe,
DoubleDouble cIm,
int maxIterations,
out int iterations
)
{
DoubleDouble zRe = DoubleDouble.Zero;
DoubleDouble zIm = DoubleDouble.Zero;
double magnitudeSquared = 0.0;
int n = 0;
for (; n < maxIterations; n++) {
DoubleDouble zReSquared = zRe.Square();
DoubleDouble zImSquared = zIm.Square();
magnitudeSquared = zReSquared.Hi + zImSquared.Hi;
if (magnitudeSquared > ESCAPE_SQUARED) {
break;
}
zIm = zRe * zIm * 2.0 + cIm;
zRe = zReSquared - zImSquared + cRe;
}
iterations = n;
return magnitudeSquared;
}
/// <summary>
/// MPFRを、一度割り当てられ、インプレースで書き込まれる宛先とともに使用します。
/// C言語で記述する場合と同様です。
/// この精度では、MPFRはスタックから一時領域を取得するため、ループは割り当てを行いません。
/// </summary>
private static double iterateInPlace(
MpfrScratch s,
int maxIterations,
out int iterations
) {
MpfrNative.SetDouble(s.ZRe, 0.0);
MpfrNative.SetDouble(s.ZIm, 0.0);
int n = 0;
for (; n < maxIterations; n++) {
MpfrNative.mpfr_sqr(s.ZReSquared, s.ZRe, MpfrNative.ROUND_NEAREST);
MpfrNative.mpfr_sqr(s.ZImSquared, s.ZIm, MpfrNative.ROUND_NEAREST);
MpfrNative.mpfr_add(s.Temp, s.ZReSquared, s.ZImSquared, MpfrNative.ROUND_NEAREST);
if (MpfrNative.mpfr_cmp(s.Temp, s.Escape) > 0) {
break;
}
MpfrNative.mpfr_mul(s.Temp, s.ZRe, s.ZIm, MpfrNative.ROUND_NEAREST);
MpfrNative.mpfr_add(s.Temp, s.Temp, s.Temp, MpfrNative.ROUND_NEAREST); // 正確な倍加
MpfrNative.mpfr_add(s.ZIm, s.Temp, s.CIm, MpfrNative.ROUND_NEAREST);
MpfrNative.mpfr_sub(s.Temp, s.ZReSquared, s.ZImSquared, MpfrNative.ROUND_NEAREST);
MpfrNative.mpfr_add(s.ZRe, s.Temp, s.CRe, MpfrNative.ROUND_NEAREST);
}
iterations = n;
// 脱出したピクセルのみがマグニチュードを使用し、その場合Tempはそれを保持しています。
// ループは再利用する行の前に終了したためです。
return MpfrNative.GetDouble(s.Temp);
}
/// <summary>
/// ワーカーごとのMPFR値。MPFR値は書き込みのためにスレッド間で共有できません。
/// そのため、<c>Parallel.For</c>のlocalInitは各ワーカーに独自のセットを提供し、
/// localFinallyで解放します。
/// </summary>
private sealed class MpfrScratch : IDisposable {
public readonly void* CRe;
public readonly void* CIm;
public readonly void* ZRe;
public readonly void* ZIm;
public readonly void* ZReSquared;
public readonly void* ZImSquared;
public readonly void* Temp;
public readonly void* Temp2;
/// <summary>MPFR値としての脱出半径。エスケープテストで変換が不要になります。</summary>
public readonly void* Escape;
public long Iterations;
public MpfrScratch(int precision) {
CRe = MpfrNative.Allocate(precision);
CIm = MpfrNative.Allocate(precision);
ZRe = MpfrNative.Allocate(precision);
ZIm = MpfrNative.Allocate(precision);
ZReSquared = MpfrNative.Allocate(precision);
ZImSquared = MpfrNative.Allocate(precision);
Temp = MpfrNative.Allocate(precision);
Temp2 = MpfrNative.Allocate(precision);
Escape = MpfrNative.Allocate(precision);
MpfrNative.SetDouble(Escape, ESCAPE_SQUARED);
}
/// <summary>すべてを解放します。両方のカーネルは、戻る際にすべての値を割り当てたままにします。</summary>
public void Dispose() {
MpfrNative.Free(CRe);
MpfrNative.Free(CIm);
MpfrNative.Free(ZRe);
MpfrNative.Free(ZIm);
MpfrNative.Free(ZReSquared);
MpfrNative.Free(ZImSquared);
MpfrNative.Free(Temp);
MpfrNative.Free(Temp2);
MpfrNative.Free(Escape);
}
}
}
double-doubleカーネルのエスケープテストはわずかに異なりますが、それは精度損失のない小さな最適化です。なぜなら、|z| > 2を過ぎた軌道は指数関数的に発散し、低位部分は反復回数に実際の影響を与えないからです。4番目のカーネル(カーネルテーブルの最後の行)は、各操作が新しい値を生成する3番目のカーネルとは異なり、スクラッチ領域に書き込むのではなく、新しい値を生成します。