Результаты отличаются при параллельном суммировании в Java

Question

Я сделал класс Sum, расширяющий RecursiveTask. Задача состоит в том, чтобы вычислить сумму 1 / a[i].

      public class Sum extends RecursiveAction {
    int[] items;
    double result;
    int min = 100000;
    int from, to;

    Sum(int[] items, int from, int to) {
        this.items = items;
        this.from = from;
        this.to = to;
    }

    @Override
    protected void compute() {
        if (to - from <= min) {
            for (int i = from; i < to; i++) {
                result += 1d / items[i];
            }
        } else {
            var mid = (from + to) / 2;
            var left = new Sum(items, from, mid);
            var right = new Sum(items, mid, to);
            invokeAll(left, right);
            result += left.result + right.result;
        }
    }
}

Полученные результаты:

      Single:   1.3180710500108106E8
Total time: 0.612
Parallel: 1.3180710501986596E8
Total time: 0.18 

Цифры очень близки и отличаются небольшой точностью. С чем это может быть связано? Я заметил, что если убрать 1/a[i], то он будет считаться правильно

Answer 1

Я предполагаю, что вы пытаетесь суммировать список из миллионов чисел. Вы написали многопоточную процедуру «разделяй и властвуй», которая прекращает деление, когда длина списка становится меньше 100000 (int min=100000;), поэтому, если стоит разделить список на куски такого размера, таких кусков должно быть хотя бы несколько, верно?

Итак, вот проблема: допустим, вы хотите сложить миллион чисел примерно одного порядка. Может быть, это все показания одного и того же датчика. Предположим, что среднее арифметическое всего списка равно X. Если бы просто пробежаться по этому списку от начала до конца, накапливая числа,...

• ... Ожидаемое значение первой суммы равно X+X,
• ...следующей суммы X+2X
• ...
• ...последней суммы X+999999X

Хорошо, но 999999X на шесть порядков больше, чем X. В двоичном формате с плавающей запятой показатель степени будет больше, чем показатель степени X примерно на 20. Другими словами, двоичное значение 999999X приблизительно равно значению X сдвинут влево на 20 бит.

Чтобы выполнить сложение, оба числа должны иметь один и тот же показатель степени, и способ, которым это достигается, заключается в денормализации X. Если вы сдвинете 999999Xмантисса X вправо на 20 бит, а затем добавите 20 к его показателю степени, он должен , теоретически, по-прежнему представляют собой одно и то же число. Единственная проблема в том, что вы только что отодвинули 20 младших битов.

Если вы используете , исходный X имел точность 54 бита, но денормализованный X, который вы можете использовать в дополнении, имеет только 34 бита. Если вы используете ,* исходный X имел 23 бита, а денормализованный X имеет только три бита точности.

---

Ваша цель при написании алгоритма «разделяй и властвуй» состояла в том, чтобы разбить проблему на задачи, которые можно было бы поручить разным потокам. Но побочным эффектом было то, что вы также получили более точный ответ. Более точно, потому что для каждого фрагмента последним шагом является вычисление X+99999X. Несовпадение показателей степени составляет всего 16 или 17 бит вместо 19 или 20 бит. Вы выбросили на три бита точности меньше.

Чтобы получить максимально возможную точность, начните с сортировки списка — сначала наименьшие числа. (ПРИМЕЧАНИЕ: наименьшее среднее значение, ближайшее к нулю — наименьшее абсолютное значение.) Затем удалите первые два числа из списка, добавьте их и вставьте сумму обратно в список в правильном месте, чтобы список оставался отсортированным. (эти вставки выполняются намного быстрее, если вы используете связанный список.) Наконец, повторяйте эти шаги, пока список не будет содержать только одно число, и это будет самая точная сумма, которую вы можете получить, не используя более широкий тип данных.

---

Более широкий тип данных!!Это то, чего вы действительно хотите. Если вы можете суммировать свою сумму в IEEE Quad float , у вас есть 112-битная точность для работы. Сложить миллион чисел? Потеряли 20 бит точности? Без проблем! 92 бита, которые вы получили в конце, по-прежнему больше, чем 54 бита в двойниках, с которых вы начали. Вы можете буквально добавить списки из триллиона чисел, прежде чем начнете терять точность по сравнению с числами с плавающей запятой.

Использование более широкого типа данных, если он у вас есть, даст вам гораздо лучшую производительность, чем сумасшедший алгоритм отсортированного списка, который я дал вам выше.

---

* Не занимайтесь математикой со значениями. Единственное применение для - это экономия места в огромных двоичных файлах и огромных массивах. Если у вас есть массив и вы хотите выполнить над ним математические операции, преобразуйте его вdouble, посчитаем и конвертируем обратно вfloatкогда вы закончите.