أفضل طريقة لتلخيص الكثير من أرقام النقطة العائمة؟

Question

تخيل أن لديك مجموعة كبيرة من أرقام النقطة العائمة، من جميع أنواع الأحجام. ما هي الطريقة الأكثر صحة لحساب المبلغ، مع أقل خطأ؟ على سبيل المثال، عندما تبدو الصفيف مثل هذا:

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

وأنت تضيف من اليسار إلى اليمين مع حلقة بسيطة مثل

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

عند إضافة الأرقام الأصغر، قد تقع الأرقام الصغيرة أسفل العتبة الدقيقة، لذلك يصبح الخطأ أكبر وأكبر. بقدر ما أعرف أفضل طريقة هي فرز الصفيف والبدء في إضافة أرقام من الأدنى إلى الأعلى، لكنني أتساءل عما إذا كانت هناك طريقة أفضل (أسرع وأكثر دقة)؟

تعديل: شكرا للإجابة، لدي الآن رمز عمل يلخص القيم المزدوجة تماما في Java. إنه ميناء مستقيم من Python Post من الإجابة الفائزة. يمر الحل جميع اختبارات وحدتي. (أطول ولكن نسخة محسنة من هذا متاح هنا 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;
    }
}

Answer 1

ل "أكثر دقة": هذه الوصفة في كتاب الطبخ بيثون لديه خوارزميات التلخيص التي تحافظ على الدقة الكاملة (عن طريق تتبع المجموعات الفرعية). الرمز في بيثون ولكن حتى لو كنت لا تعرف Python، فمن الواضح بما يكفي للتكيف مع أي لغة أخرى.

يتم تقديم جميع التفاصيل في هذه الورقة.

Answer 2

أنظر أيضا: خوارزمية لتجمع كاهان لا يتطلب O (N) التخزين ولكن فقط O (1).

Answer 3

هناك العديد من الخوارزميات، اعتمادا على ما تريد. عادة ما تتطلب تتبع المبالغ الجزئية. إذا حافظت على Summs x [k + 1] - x [k]، تحصل على خوارزمية كاهان. إذا كنت تتبع جميع المبالغ الجزئية (من هنا، فستنتج خوارزمية O (n ^ 2)، فاحصل على إجابة DF.

لاحظ أنه بالإضافة إلى مشكلتك، تلخيص أرقام علامات مختلفة مشكلة جدا.

الآن، هناك وصفات أبسط من تتبع جميع المبالغ الجزئية:

• فرز الأرقام قبل تلخيصها، أو مجموع كل السلبيات والإيجابيات بشكل مستقل. إذا كنت قد قمت بفرز الأرقام، فغرم، وإلا لديك خوارزمية O (N Log N). مجموع عن طريق زيادة الحجم.
• مجموع بواسطة أزواج، ثم أزواج من أزواج، إلخ.

تظهر التجربة الشخصية أنك عادة لا تحتاج إلى أشياء مربعة من طريقة كاهان.

Answer 4

حسنا، إذا كنت لا ترغب في الترتيب، فيمكنك ببساطة إبقاء المجموع في متغير مع نوع من الدقة الأعلى من القيم الفردية (مثل استخدام مزدوج للحفاظ على مجموع العوامات، أو "رباعية" للحفاظ على مجموع الزوجي). سيفرض ذلك عقوبة في الأداء، ولكن قد يكون أقل من تكلفة الفرز.

Answer 5

إذا كان طلبك يعتمد على البحث الرقمي البحث عن مكتبة حسابية تعسفية دقيقة، فلا أعرف إذا كانت هناك مكتبات بيثون من هذا النوع. بالطبع، كل هذا يتوقف على عدد الأرقام الدقيقة التي تريدها - يمكنك تحقيق نتائج جيدة مع النقطة العائمة IEEE القياسية إذا كنت تستخدمها بعناية.