いかに多くの浮動小数点数?

StackOverflow https://stackoverflow.com/questions/394174

質問

たとえば大型の配列の浮動小数点の場合には、すべての種類のサイズです。その中で最も正しい計算の和が最も少ない。例えば、配列のようになります。

[1.0, 1e-10, 1e-10, ... 1e-10.0]

ます左から右へと単純なループように、

sum = 0
numbers.each do |val|
    sum += val
end

きの追加は小さい番号が以下の精度しきい値の誤差が大きました。私の知るかぎりの最良の方法でソートすることも可能で配列の開始を足し合わせるリダクション数の最下位から最上位へ向かってがんがあればもっといいもの（より速く、より精度の高い)?

編集:の答えは、私たいコードと完璧に関するdouble値をJava.で直港からPythonのポストの答えです。の解決すべてのユニット。(長が最適なのはこちら Summarizer.java)

/**
 * Adds up numbers in an array with perfect precision, and in O(n).
 * 
 * @see http://code.activestate.com/recipes/393090/
 */
public class Summarizer {

    /**
     * Perfectly sums up numbers, without rounding errors (if at all possible).
     * 
     * @param values
     *            The values to sum up.
     * @return The sum.
     */
    public static double msum(double... values) {
        List<Double> partials = new ArrayList<Double>();
        for (double x : values) {
            int i = 0;
            for (double y : partials) {
                if (Math.abs(x) < Math.abs(y)) {
                    double tmp = x;
                    x = y;
                    y = tmp;
                }
                double hi = x + y;
                double lo = y - (hi - x);
                if (lo != 0.0) {
                    partials.set(i, lo);
                    ++i;
                }
                x = hi;
            }
            if (i < partials.size()) {
                partials.set(i, x);
                partials.subList(i + 1, partials.size()).clear();
            } else {
                partials.add(x);
            }
        }
        return sum(partials);
    }

    /**
     * Sums up the rest of the partial numbers which cannot be summed up without
     * loss of precision.
     */
    public static double sum(Collection<Double> values) {
        double s = 0.0;
        for (Double d : values) {
            s += d;
        }
        return s;
    }
}
役に立ちましたか？

解決

は、「より正確に」：保つ加算アルゴリズムを持っていにはPythonクックブックで、このレシピ（小計を追跡することによって）完全精度。コードはPythonであるが、あなたは、Pythonを知らない場合でも、それは他の言語に適応するために十分に明確だ。

すべての詳細は、<のhref = "http://www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps" のrel = "noreferrerに記載されています「>この論文でます。

他のヒント

カハンの加算アルゴリズムalgorithm">

多くのアルゴリズムによっては、と考えている。通常必要な身体の安全を確保するため得られた。続けていくだけの金額x[k+1]x[k]、河畔アルゴリズムです。すべての得られる降伏にはO(n^2)のアルゴリズム)、@dF'sの答えです。

注するための問題を総括数 異なる兆し は非常に問題がある。

現在は、より簡単なレシピにより身体の安全を確保するためのすべての部分額:

  • ソート番号の前に総括にて、和のすべてのネガのブindependantly.い順にソート番号、その他すO(n log n)アルゴリズムです。和増大きくなりました。
  • 和によるペアを組のペアが等

個人的経験が示すようご通常必要がないローカル色の強いものより河畔の方法です。

あなたが並べ替えしたくない場合さて、あなたは単に山車の合計、または「クワッド」を維持するために、二重を使用します（例：個々の値よりも高精度の型の変数に合計を保つことができますダブルスの合計を維持します）。これは、パフォーマンスペナルティを課すだろうが、それは、ソートのコストよりも少ないかもしれません。

この種のPythonライブラリがある場合は、

あなたのアプリケーションが任意精度演算ライブラリの数値処理の検索に依存している場合は、しかし、私は知りません。もちろん、すべてはあなたが望むどのように多くの精度桁数に依存して - 。あなたは注意して使用する場合は、標準のIEEE浮動小数点との良好な結果を得ることができます。

所属していません StackOverflow
scroll top