Комментарии 9
Спасибо, хорошая статья, и напоминание про подобные грабли (на примере наивного подхода) не лишнее.
Сам такой подход люблю, особенно для сглаживающих цифровых фильтров (когда разрядов мало), но не знал названия.
Однако же попробуйте метод (для float) на последовательности из миллиона единиц, потом миллион двоек…
Ну или более реальный случай — миллион чисел, плавно растущих от 1 до 2.
Отличный пример, спасибо! Действительно, можно "сломать" метод, если разрядности не хватает для представления результата суммирования с нормированной разностью. В такой ситуации можно было бы использовать счётчик Кахана внутри метода Уэлфорда. Но я бы не стал рекомендовать такой способ в качестве стандартного, т.к. очень уж большие накладные расходы.
А какой метод используете вы в описанной ситуации?
счётчик Кахана
А что это за зверь, если не секрет? Гугл не помогает.
Я вот об этом :) Вероятно, мешает моя привычка называть автора Каханом, а его алгоритм — счётчиком.
https://ru.wikipedia.org/wiki/Алгоритм_Кэхэна
Сама эта тема оказалась настолько для меня интересной, что я потом даже диссертацию про это написал.
По ссылке ожидал увидеть PDF, но не 120-мегабайтный архив с чем-то, похожим на профиль браузера вместе с кешем. Это точно именно то, что вы имели в виду?
void perr(const std::string& type, double v, double u) {
double abs_e = std::abs(v - u);
std::cout << type << " abs: " << abs_e << " rel: " << abs_e / u << std::endl;
};
void test_m(const size_t n = 100000000, double from = 128, double step = 1) {
double m = from + step * (n - 1) / (2 * n);
MeanDummy m0;
MeanKahan m1;
MeanWelford m2;
for (size_t i = 0; i < n; ++i) {
double v = from + i * step / n;
m0.add(v);
m1.add(v);
m2.add(v);
}
std::cout << "test mean\n";
perr("Dummy", m0.mean(), m);
perr("Kahan", m1.mean(), m);
perr("Welford", m2.mean(), m);
}
void test_c(const size_t n = 100000000, double from0 = 128, double step0 = 3, double from1 = 32, double step1 = 2) {
double c = step0 * step1 / 12 * (1 - 1.0/(n * n));
CovariationDummy c0;
CovariationKahan c1;
CovariationWelford c2;
CovariationWelford2 c3;
CovariationWelfordKahan c4;
for (size_t i = 0; i < n; ++i) {
double v = from0 + i * step0 / n;
double u = from1 + i * step1 / n;
c0.add(v, u);
c1.add(v, u);
c2.add(v, u);
c3.add(v, u);
c4.add(v, u);
}
std::cout << "test covariation\n";
perr("Dummy", c0.covariation(), c);
perr("Kahan", c1.covariation(), c);
perr("Welford", c2.covariation(), c);
perr("Welford2", c3.covariation(), c);
perr("WelfordKahan", c4.covariation(), c);
}
test mean
Dummy abs: 2.84217e-14 rel: 2.21181e-16
Kahan abs: 0 rel: 0
Welford abs: 3.96642e-07 rel: 3.0867e-09
test covariation
Dummy abs: 1.55029e-10 rel: 3.10059e-10
Kahan abs: 6.10456e-13 rel: 1.22091e-12
Welford abs: 1.18424e-07 rel: 2.36848e-07
Welford2 abs: 1.18424e-07 rel: 2.36848e-07
WelfordKahan abs: 0 rel: 0
По-моему, эту ситуацию обсуждали выше: https://habrahabr.ru/post/333426/#comment_10325964.
Точное вычисление средних и ковариаций методом Уэлфорда