Добавление с плавающей точкой: проблемы потери точности - PullRequest
Новая
       6

Добавление с плавающей точкой: проблемы потери точности

9 голосов
/ 10 августа 2009

Вкратце: как я могу выполнить a+b так, чтобы любая потеря точности из-за усечения была от нуля , а не к нулю?

Длинная история

Я вычисляю сумму длинного ряда значений с плавающей запятой с целью вычисления среднего значения выборки и дисперсии множества. Поскольку Var (X) = E (X 2 ) - E (X) 2 , достаточно поддерживать счет числа всех чисел, сумму всех числа на данный момент и сумма квадратов всех чисел на данный момент.

Пока все хорошо.

Однако абсолютно необходимо, чтобы E (X 2 )> E (X) 2 , что из-за точности с плавающей запятой не всегда дело. В псевдокоде проблема заключается в следующем: 

int count;
double sum, sumOfSquares;
...
double value = <current-value>;
double sqrVal = value*value; 

count++;
sum += value; //slightly rounded down since value is truncated to fit into sum
sumOfSquares += sqrVal; //rounded down MORE since the order-of-magnitude 
//difference between sqrVal and sumOfSquares is twice that between value and sum;

Для переменных последовательностей это не большая проблема - в итоге вы немного недооцениваете дисперсию, но часто это не большая проблема. Однако для постоянных или почти постоянных наборов с ненулевым средним значением это может означать, что E (X 2 ) 2 , в результате получается отрицательная вычисленная дисперсия, которая нарушает ожидания потребления кода.

Теперь я знаю о суммировании Кахана, которое не является привлекательным решением. Во-первых, это делает код восприимчивым к капризам оптимизации (в зависимости от флагов оптимизации, код может проявлять или не проявлять эту проблему), а во-вторых, проблема не в действительно из-за точности - что достаточно хорошо - это потому, что сложение вносит систематическую ошибку в сторону нуля. Если бы я мог выполнить строку 

sumOfSquares += sqrVal;

таким образом, чтобы гарантировать, что sqrVal округлен, а не уменьшен до точности sumOfSquares, у меня было бы численно разумное решение. Но как мне этого достичь?

Изменить: Законченный вопрос - почему нажатие клавиши ввода в раскрывающемся списке в поле тега так или иначе отправляет вопрос?

Ответы [ 3 ]

6 голосов
/ 10 августа 2009

Есть еще один однопроходный алгоритм, который немного перестраивает вычисления. В псевдокод: 

n = 0
mean = 0
M2 = 0

for x in data:
    n = n + 1
    delta = x - mean
    mean = mean + delta/n
    M2 = M2 + delta*(x - mean)  # This expression uses the new value of mean

variance_n = M2/n         # Sample variance
variance = M2/(n - 1)     # Unbiased estimate of population variance

(Источник: http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance)

Кажется, лучше вести себя в отношении проблем, которые вы указали с обычным алгоритмом.

6 голосов
/ 10 августа 2009

IEEE предоставляет четыре режима округления (в направлении -inf, в направлении + inf, в направлении 0, наиболее тонально). К + инфу это то, чего ты хочешь. В C90 или C ++ нет стандартного управления. C99 добавил заголовок <fenv.h>, который также присутствует как расширение в некоторых реализациях C90 и C ++. Чтобы соблюдать стандарт C99, вам нужно написать что-то вроде: 

#include <fenv.h>
#pragma STDC FENV_ACCESS ON

int old_round_mode = fegetround();
int set_round_ok = fesetround(FE_UPWARD);
assert(set_round_ok == 0);
...
int set_round_ok = fesetround(old_round_mode);
assert(set_round_ok == 0);

Хорошо известно, что алгоритм, который вы используете, численно нестабилен и имеет проблему точности. Для точности лучше выполнить два прохода данных.

2 голосов
/ 10 августа 2009

Если вы не беспокоитесь о точности, а только о отрицательной дисперсии, почему бы вам просто не сделать V(x) = Max(0, E(X^2) - E(X)^2)

...