Я использую суммирование Кахана для интеграции Монте-Карло. У вас есть скалярная функция 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 не может быть увеличено в разумные сроки на современном оборудовании.