Как я могу добавить плавания вместе в различных заказах и всегда получать то же общее количество?
Скажем, у меня есть три 32-разрядных значения с плавающей точкой, a, b, и c, таким образом, что (a + b) + c != a + (b + c). Существует ли алгоритм суммирования, возможно, подобный суммированию Kahan, которое гарантирует, что эти значения могут быть суммированы в порядке и всегда прибывать в то же самое (довольно точное) общее количество? Я ищу общий случай (т.е. не решение, которое только имеет дело с 3 числами).
Действительно ли арифметика произвольной точности является единственным способом пойти? Я имею дело с очень большими наборами данных, таким образом, я хотел бы избежать издержек использования арифметики произвольной точности, если это возможно.
Спасибо!
3 ответа
Здесь есть интересный алгоритм «суммирования с полной точностью» , который гарантирует, что окончательная сумма не зависит от порядка слагаемых (рецепт дан на Python; но его не должно быть слишком сложно перевести на другие языки). Обратите внимание, что рецепт, приведенный в этой ссылке, не совсем верен: основной цикл накопления хорош, но на последнем шаге, который преобразует список накопленных частичных сумм в один результат с плавающей запятой (самая последняя строка msum recipe), чтобы получить правильно округленный результат, нужно быть немного осторожнее, чем просто суммировать частичные суммы. См. Комментарии под рецептом и реализацию Python (ссылка ниже), чтобы узнать, как это исправить.
Он действительно использует форму арифметики произвольной точности для хранения частичных сумм (промежуточные суммы представлены как «неперекрывающиеся» суммы удвоений), но, тем не менее, может быть достаточно быстрым, особенно когда все входы примерно одинаковой величины. И он всегда дает правильно округленный результат, поэтому точность настолько хороша, насколько вы можете надеяться, а окончательная сумма не зависит от порядка слагаемых. Он основан на этой статье (Адаптивная точная арифметика с плавающей запятой и быстрые надежные геометрические предикаты) Джонатана Шевчука.
Python использует этот алгоритм для математической реализации.fsum, который выполняет суммирование, не зависящее от порядка, с правильным округлением; вы можете увидеть реализацию C, которую использует Python здесь --- найдите функцию math_fsum.
Имея некоторую дополнительную информацию о терминах, которые необходимо суммировать, вы можете избежать накладных расходов на алгоритм Шевчука.
В арифметике IEEE 754 xy является точным всякий раз, когда y / 2 <= x <= 2 * y (теорема Стербенца, формально доказанная здесь )
Итак, если вы можете расположить все свои термины в таком порядке, чтобы каждая частичная сумма имела форму, указанную выше, то вы получите точный результат бесплатно.
Боюсь, что на практике мало шансов оказаться в условиях, когда это обязательно произойдет. Чередование положительных и отрицательных чисел с увеличением величины может быть одним из случаев, когда это происходит.
Примечание: исходный вопрос касался алгоритма, который давал бы один и тот же результат независимо от порядка суммирования. Ответ Марка вызвал сдвиг в сторону «точного алгоритма», но, читая еще раз ваш вопрос, я боюсь, что захожу слишком далеко, предлагая изменить порядок условий. Вы, вероятно, не можете сделать то, что пытаетесь сделать, и мой ответ, вероятно, не по теме. Что ж, извините :)
Я не совсем уверен, что ( a + b) + c! = a + (b + c) при выполнении арифметических действий в программе.
Однако практическое правило использования арифметики с плавающей запятой на современном оборудовании состоит в том, чтобы никогда не проверять равенство напрямую.
Для любого приложения вы должны выбрать достаточно маленький эпсилон и использовать
(abs(a - b) < epsilon)
в качестве теста на равенство.