Как я могу добавить поплавки вместе в разных порядках и всегда получать одинаковое количество?

Question

Скажем, у меня есть три 32-битных значения с плавающей запятой, a, b и c, такие что (a + b) + c != a + (b + c). Существует ли алгоритм суммирования, возможно, похожий на суммирование Кахана , который гарантирует, что эти значения могут быть суммированы в любом порядке и всегда приводят к одной и той же (довольно точной) сумме? Я ищу общий случай (т.е. не решение, которое имеет дело только с 3 числами).

Является ли арифметика произвольной точности единственным путем? Я имею дело с очень большими наборами данных, поэтому я хотел бы избежать накладных расходов на использование арифметики произвольной точности, если это возможно.

Спасибо!

Answer 1

Есть интересный алгоритм суммирования с полной точностью здесь , который гарантирует, что окончательная сумма не зависит от порядка слагаемых (рецепт дан на Python; но это не должно быть слишком сложно переводить на другие языки). Обратите внимание, что рецепт, приведенный в этой ссылке, не совсем корректен: основной цикл накопления в порядке, но на последнем шаге преобразование списка накопленных частичных сумм в один результат с плавающей запятой (самая последняя строка msum рецепт), нужно быть немного более осторожным, чем просто суммировать частичные суммы, чтобы получить правильно округленный результат. См. Комментарии под рецептом и реализацию Python (см. Ниже), чтобы узнать, как это исправить.

В используется форма арифметики произвольной точности для хранения частичных сумм (промежуточные суммы представляются как «непересекающиеся» суммы двойников), но, тем не менее, могут быть достаточно быстрыми, особенно когда входы примерно одинаковой величины. И это всегда дает правильно округленный результат, так что точность настолько хороша, насколько вы можете надеяться, и окончательная сумма не зависит от порядка слагаемых. Он основан на этой статье (Арифметическая адаптивная прецизионная арифметика и быстрые робастные геометрические предикаты) Джонатана Шевчука.

Python использует этот алгоритм для реализации math.fsum, который выполняет правильно округленное суммирование, не зависящее от порядка; вы можете увидеть реализацию C, которую Python использует здесь --- ищите функцию math_fsum.

Answer 2

С некоторой дополнительной информацией о слагаемых, которые вы должны суммировать, вы можете избежать издержек алгоритма Шевчука.

В арифметике IEEE 754 x-y является точным всякий раз, когда y/2 <= x <= 2*y (теорема Стербенса, формально доказанная здесь )

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

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

Примечание. Первоначальный вопрос касался алгоритма, который давал бы один и тот же результат независимо от порядка суммирования. Ответ Марка вызвал отклонение в сторону «точного алгоритма», но, перечитывая ваш вопрос, я боюсь, что слишком далеко захожу, когда предлагаю изменить порядок слов. Вы, вероятно, не можете в том, что вы пытаетесь сделать, и мой ответ, вероятно, не по теме. Ну, извините:)

Answer 3

Я не совсем уверен, что (a + b) + c! = A + (b + c) при выполнении арифметики в программе.

Тем не менее, практическое правило с использованием арифметики с плавающей точкой в ​​настоящее времяСегодня аппаратное обеспечение никогда не должно напрямую проверяться на равенство.

Для любого приложения, которое у вас есть, вы должны выбрать достаточно малый эпсилон и использовать

(abs(a - b) < epsilon)

в качестве теста на равенство.