Суммирование Кахана - PullRequest
       2

Суммирование Кахана

4 голосов
/ 09 февраля 2011

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

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

Ответы [ 3 ]

6 голосов
/ 09 февраля 2011

Суммирование Кахана хорошо работает, когда вы суммируете числа, и вам нужно минимизировать ошибку с плавающей точкой в ​​худшем случае. Без этой техники вы можете значительно потерять точность в операциях добавления, если у вас есть два числа, которые отличаются по величине доступными значащими цифрами (например, 1 + 1e-12). Суммирование Кахана компенсирует это.

И отличный ресурс по проблемам с плавающей запятой здесь, "Что должен знать каждый специалист по информатике о с плавающей запятой": http://www.validlab.com/goldberg/paper.pdf

Для производительности с одинарной или двойной точностью: да, одинарная точность может быть значительно выше, но это зависит от конкретной машины. Смотри: http://www.hpcwire.com/features/17885244.html

Лучший способ проверить это - написать короткий пример, который проверяет операции, которые вам интересны, с одинарной (плавающей) и двойной точностью, и измеряет время выполнения.

1 голос
/ 07 сентября 2016

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

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

Однако я заметил довольно большие1e-3) ошибки при выполнении умножения обратной матрицы.По сути, A*x = y, а затем inv(A)*y ~= x Я не получаю исходные значения точно.Это хорошо, но я подумал, что суммирование по Кахану поможет (есть много сложений), особенно с большими матрицами> 3 на 3.Я попытался с матрицей 4 на 4, и это совсем не улучшило ситуацию.

0 голосов
/ 07 января 2019

Я использую суммирование Кахана для интеграции Монте-Карло. У вас есть скалярная функция f, которую вы считаете довольно дорогой для оценки; разумная оценка составляет 65 нс / размерность. Затем вы накапливаете эти значения в среднем. Обновление в среднем занимает около 4 нс. Поэтому, если вы обновляете среднее с помощью суммирования по Кахану (в 4 раза больше флопов, ~ 16 нс), тогда вы на самом деле не добавляете столько вычислений к общему количеству. Сейчас часто говорят, что ошибка интеграции Монте-Карло - & sigma; / & # x221a; N , но это неверно. Реальная граница ошибки (в арифметике конечной точности) составляет

& sigma; / & # x221a; N + cond ( I n ) & epsilon; N

Где cond ( I n ) - номер условия суммирования и & epsilon; в два раза больше единицы. Таким образом, алгоритм расходится быстрее, чем сходится . Для 32-битной арифметики, получая & epsilon; N ~ 1 прост: 10 ^ 7 оценок могут быть выполнены очень быстро, и после этого ваша интеграция Монте-Карло идет на случайную прогулку. Ситуация еще хуже, когда номер условия большой.

Если вы используете суммирование Кахана, выражение для ошибки изменится на

& sigma; / & # x221a; N + cond ( I n ) & epsilon; 2 N

Который, по общему признанию, все еще расходится быстрее, чем сходится, но & epsilon; 2 N не может быть увеличено в разумные сроки на современном оборудовании.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...