Ваш инстинкт в принципе правильный, сортировка по возрастанию (по величине) обычно несколько улучшает ситуацию. Рассмотрим случай, когда мы добавляем 32-битные числа с одинарной точностью, и 1 миллиард значений равен 1 / (1 миллиард), а одно значение равно 1. Если 1 стоит первым, то сумма будет 1, поскольку 1 + (1/1 млрд.) - 1 из-за потери точности. Каждое добавление никак не влияет на общее количество.
Если маленькие значения появятся первыми, они, по крайней мере, будут суммироваться с чем-то, хотя даже тогда у меня их 2 ^ 30, тогда как после 2 ^ 25 или около того я снова в ситуации, когда каждое из них не является индивидуальным. влияет на общее количество больше. Так что мне все еще нужно больше трюков.
Это крайний случай, но в общем случае сложение двух значений одинаковой величины является более точным, чем добавление двух значений очень разных величин, поскольку таким образом вы «отбрасываете» меньше битов точности при меньшем значении. Сортируя числа, вы группируете значения одинаковой величины вместе, и, добавляя их в порядке возрастания, вы даете маленьким значениям «шанс» совокупного достижения величины больших чисел.
Тем не менее, если задействованы отрицательные числа, такой подход легко перехитрить. Рассмотрим три значения для суммирования, {1, -1, 1 billionth}. Арифметически правильная сумма равна 1 billionth, но если мое первое добавление включает в себя крошечное значение, то моя итоговая сумма будет равна 0. Из 6 возможных ордеров только 2 являются «правильными» - {1, -1, 1 billionth} и {-1, 1, 1 billionth}. Все 6 заказов дают результаты, которые являются точными в масштабе наибольшего значения во входных данных (0,0000001%), но для 4 из них результат является неточным в масштабе истинного решения (100%). Конкретная проблема, которую вы решаете, скажет вам, достаточно ли она хороша или нет.
На самом деле, вы можете играть намного больше трюков, чем просто добавлять их в отсортированном порядке. Если у вас есть много очень маленьких значений, среднее число средних значений и небольшое количество больших значений, то, возможно, будет наиболее точным сначала сложить все маленькие, а затем отдельно сложить средние значения, добавить эти два итога. вместе затем добавьте большие. Найти совсем точную комбинацию сложений с плавающей точкой совсем не тривиально, но чтобы справиться с действительно плохими случаями, вы можете сохранить целый массив промежуточных сумм с разными величинами, добавляя каждое новое значение к сумме, которая лучше всего соответствует его величине, и когда промежуточный итог начинает становиться слишком большим для его величины, добавьте его в следующий итог и начните новый. Взятый до логического предела, этот процесс эквивалентен выполнению суммы в типе с произвольной точностью (так что вы бы это сделали). Но, учитывая упрощенный выбор сложения в порядке возрастания или убывания, лучше сделать ставку по возрастанию.
Это имеет какое-то отношение к программированию в реальном мире, поскольку в некоторых случаях ваши вычисления могут пойти очень плохо, если вы случайно отрубите «тяжелый» хвост, состоящий из большого числа значений, каждое из которых слишком мало индивидуально влиять на сумму, или если вы отбрасываете слишком много точности из множества маленьких значений, которые по отдельности влияют только на последние несколько битов суммы. В тех случаях, когда хвост в любом случае незначителен, вам, вероятно, все равно. Например, если вы сначала складываете небольшое количество значений и используете только несколько значащих цифр суммы.