algorithm - 繰り返し操作による丸め誤差の影響を効果的に最小限に抑える

Question

私は最近、丸めを最小化するためのカハン（または補償）加算アルゴリズムに出くわしました。除算および/または乗算、および減算（ある場合は、私は知っています）に同等のアルゴリズムがあるかどうかを知りたいです。連想性について）。任意の言語、擬似コード、またはリンクでの実装例は素晴らしいでしょう！

ありがとう

Answer 1

減算は通常、カハン法を介して処理されます。

乗算には、2つの浮動小数点数の積を丸めずに2つの浮動小数点数の合計に変換するアルゴリズムがあります。その時点で、次に何をする必要があるかに応じて、カハンの加算またはその他の方法を使用できます。製品。

FMA（fused multiply-add）を使用できる場合、これは次のように簡単に実行できます。

p = a*b;
r = fma(a,b,-p);

これらの2つの操作の後、オーバーフローまたはアンダーフローが発生しない場合は、丸めなしp + rとまったく同じになります。a * bこれはFMAなしでも達成できますが、かなり困難です。これらのアルゴリズムに興味がある場合は、それらのいくつかの詳細が記載されたcrlibm ドキュメントをダウンロードすることから始めることができます。

分割...まあ、分割は避けるのが最善です。分割は遅く、補正された分割はさらに遅くなります。あなたはそれを行うことができますが、FMAなしでは残酷に困難であり、それを使用することは簡単ではありません。可能な限り回避するようにアルゴリズムを設計することをお勧めします。

これらすべてがすぐに敗戦になることに注意してください。これらのトリックが有益な状況は非常に狭い範囲にあります。より複雑な場合は、mpfrのような高精度の浮動小数点ライブラリを使用する方がはるかに優れています。あなたがその分野の専門家でない限り（または1人になりたいと思っているのでない限り）、通常はそのようなライブラリの使い方を学ぶのが最善です。

Answer 2

数値的に安定するようにアルゴリズムを設計することは、それ自体が学問分野であり、研究分野です。これは、「チートシート」を介して意味のある方法で実行（または学習）できるものではありません。特定の数学的知識が必要であり、特定のアルゴリズムごとに実行する必要があります。これを行う方法を学びたい場合は、ウィキペディアの記事の参照がかなり良いように聞こえます：Nicholas J. Higham、数値アルゴリズムの精度と安定性、Society of Industrial and Applied Mathematics、フィラデルフィア、1996年。ISBN0-89871-355- 2.2。

アルゴリズムの安定性を診断する比較的簡単な方法は、区間演算を使用することです。

Answer 3

浮動小数点数ではなく、ビッグナムと有理分数を使用できます。その場合、必要な精度を保持するためのメモリの有限の可用性によってのみ制限されます。