Pertanyaan Bagaimana cara terbaik untuk menjumlahkan banyak angka floating point?


Bayangkan Anda memiliki sejumlah besar angka floating point, dari semua jenis ukuran. Apa cara yang paling benar untuk menghitung jumlah, dengan kesalahan terkecil? Misalnya, ketika array terlihat seperti ini:

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

dan Anda menambahkan dari kiri ke kanan dengan loop sederhana, seperti

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

setiap kali Anda menambahkan angka yang lebih kecil mungkin jatuh di bawah ambang batas presisi sehingga kesalahan semakin besar dan semakin besar. Sejauh yang saya tahu cara terbaik adalah mengurutkan array dan mulai menambahkan angka dari yang terendah hingga tertinggi, tetapi saya bertanya-tanya apakah ada cara yang lebih baik (lebih cepat, lebih tepat)?

EDIT: Terima kasih atas jawabannya, saya sekarang memiliki kode kerja yang sempurna meringkas nilai ganda di Java. Ini adalah port lurus dari pos Python dari jawaban pemenang. Solusinya memberikan semua tes unit saya. (Versi yang lebih panjang tetapi dioptimalkan ini tersedia di sini 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;
    }
}

32
2017-12-26 19:40


asal


Jawaban:


Untuk "lebih tepat": resep ini di Python Cookbook memiliki algoritme penjumlahan yang menjaga ketepatan penuh (dengan melacak subtotal). Kode dalam Python tetapi bahkan jika Anda tidak tahu Python cukup jelas untuk beradaptasi dengan bahasa lain.

Semua rincian diberikan kertas ini.


24
2017-12-26 19:46



Lihat juga: Algoritma penjumlahan Kahan Tidak memerlukan penyimpanan O (n) tetapi hanya O (1).


12
2018-01-27 22:30



Ada banyak algoritme, tergantung apa yang Anda inginkan. Biasanya mereka membutuhkan pelacakan jumlah parsial. Jika Anda hanya menyimpan jumlah x [k + 1] - x [k], Anda mendapatkan algoritma Kahan. Jika Anda melacak semua jumlah parsial (sehingga menghasilkan O (n ^ 2) algoritma), Anda mendapatkan jawaban @ dF.

Perhatikan bahwa selain masalah Anda, menjumlahkan angka tanda-tanda yang berbeda sangat bermasalah.

Sekarang, ada resep yang lebih sederhana daripada melacak semua jumlah parsial:

  • Urutkan angka-angka sebelum menjumlahkan, jumlah semua negatif dan positif secara independen. Jika Anda telah mengurutkan angka, baik-baik saja, jika tidak Anda memiliki O (n log n) algoritma. Jumlahkan dengan meningkatkan besaran.
  • Jumlahkan dengan pasangan, lalu pasang pasangan, dll.

Pengalaman pribadi menunjukkan bahwa Anda biasanya tidak membutuhkan hal yang lebih mewah daripada metode Kahan.


2
2017-12-30 14:07



Nah, jika Anda tidak ingin mengurutkan maka Anda bisa menjaga total dalam variabel dengan jenis presisi yang lebih tinggi daripada nilai-nilai individu (misalnya menggunakan ganda untuk menjaga jumlah pelampung, atau "quad" untuk menjaga jumlah ganda). Ini akan menjatuhkan hukuman kinerja, tetapi mungkin kurang dari biaya penyortiran.


0
2017-12-26 21:02



Jika aplikasi Anda bergantung pada pencarian pemrosesan numerik untuk pustaka aritmatika presisi arbitrer, namun saya tidak tahu apakah ada pustaka Python semacam ini. Tentu saja, semua tergantung pada berapa banyak digit presisi yang Anda inginkan - Anda dapat mencapai hasil yang baik dengan standar floating point IEEE jika Anda menggunakannya dengan hati-hati.


0
2017-12-26 21:09