Сумма сумм арифметических прогрессий

Ну незнаю. Так то формулировка вполне известная: "Задача о шарах и перегородках", А S_l(n) \eq C_n^l, число сочетаний. Другая формулировка: число решений уравнения \sum_{i = 1}^{l+1}{x_i} \eq N-l, x_i \in \mathbb{N}_0, в ней ваше доп условие про r задается так x_i < r (если вычесть из общего числа вариантов). Теперь методом динамического программирования должно получиться простое решение за O(nl*bigint_add) (чтобы получилось без r нужно сумму на отрезке выразить через предыдущее значение) которое выглядит естественнее того что написано в статье. Возможно с мемоизацией ваше решение не так уж и плохо, но точно выглядит ужасно.

Точное вычисление средних и ковариаций методом Уэлфорда

Не впечатлил что-то ваш Уэлфорд.

code

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