Хабы: Математика, Программирование, Алгоритмы, Rust, Компиляторы
Допустим, у нас есть массив чисел с плавающей запятой, и мы хотим их суммировать. Можно наивно подумать, что их достаточно просто сложить, например, на Rust.
Однако это запросто может привести к произвольно большой накопленной погрешности. Давайте проверим:
naive_sum(&vec![1.0; 1_000_000]) = 1000000.0
naive_sum(&vec![1.0; 10_000_000]) = 10000000.0
naive_sum(&vec![1.0; 100_000_000]) = 16777216.0
naive_sum(&vec![1.0; 1_000_000_000]) = 16777216.0
Ой-ёй… Что произошло? Проблема в том .что следующее 32-битное число с плавающей запятой после 16777216
— это 16777218
. Так что при вычислении 16777216 + 1
, значение округляется до ближайшего числа с плавающей запятой, имеющей чётную мантиссу, то есть снова до 16777216
. Мы зашли в тупик.
К счастью, есть более совершенные способы суммирования массива.
Читать далее