rolling-sum.cpp

#include <cmath>
#include <cstdint>

#include <random>
#include <iostream>


template<typename Float, int N>
class log_sum {
    static_assert(N > 0, "N must be positive");

    Float regs_[N] = {0};

    void rebalance() {
        for (int i = 0; i < N-1; i++) {
            if (regs_[i] > regs_[i + 1]) {
                regs_[i + 1] += regs_[i];
                regs_[i] = 0;
            }
        }
    }

public:
    log_sum(Float initial) {
        regs_[N-1] = initial;
    }

    log_sum<Float, N> &operator +=(Float value) {
        regs_[0] += value;
        rebalance();
        return *this;
    }
    
    Float get() const {
        Float sum = 0;
        for (int i = N - 1; i >= 0; i--) {
            sum += regs_[i];
        }
        return sum;
    }

    explicit operator int64_t() const {
        return get();
    }
};


template<typename Approx, typename Precise = uint64_t>
void test_sum(uint64_t count) {
    Precise precise_sum = 0;
    Approx approx_sum = 0;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<Precise> sample(77, 8888);

    std::cout << "Calculating..." << std::flush;
    for (uint64_t i = 0; i < count; i++) {
        auto value = sample(gen);
        precise_sum += value;
        approx_sum += value;
    }
    std::cout << " OK" << std::endl;

    auto actual_approx_sum = static_cast<Precise>(approx_sum);
    auto delta = precise_sum - actual_approx_sum;
    std::cout << "precise sum = " << precise_sum << std::endl;
    std::cout << " approx sum = " << actual_approx_sum << std::endl;
    std::cout << "      delta = " << delta << std::endl;
    std::cout << "        eps = " << (double(delta) * 100 / precise_sum) << "%" << std::endl;
}


int main(int argc, char *argv[]) {
    if (argc != 2) {
        return 1;
    }

    auto count = std::stoull(argv[1]);
    test_sum<float, int64_t>(count);
    test_sum<log_sum<float, 8>, int64_t>(count);
    return 0;
}

stdout

% ./a.out 10000000 
Calculating... OK
precise sum = 44823223329
 approx sum = 44640296960
      delta = 182926369
        eps = 0.408106%
Calculating... OK
precise sum = 44821836212
 approx sum = 44821831680
      delta = 4532
        eps = 1.01111e-05%

% ./a.out 100000000
Calculating... OK
precise sum = 448212445276
 approx sum = 226911027200
      delta = 221301418076
        eps = 49.3742%
Calculating... OK
precise sum = 448245944805
 approx sum = 448239894528
      delta = 6050277
        eps = 0.00134977%

% ./a.out 1000000000
Calculating... OK
precise sum = 4482442329322
 approx sum = 274877906944
      delta = 4207564422378
        eps = 93.8677%
Calculating... OK
precise sum = 4482429756514
 approx sum = 4480073465856
      delta = 2356290658
        eps = 0.0525673%