2
\$\begingroup\$

The basic "running averager" is familiar, both in embedded as well as real-time applications such as games, eg for fps. This algorithm is implemented in many microcontrollers (notably the PIC series) for analog input averaging. This is a software replacement.

Usage: We feed sample values using operator() and the current "running average" is returned on each call. max_samples determines the "time-constant" of the averaging. The higher, the smoother the the output. We don't need to store the samples, as we can calculate the new sum by subtracting the previous avg and adding the new_value.

In order not to have a distorted avg for (at least) the first max_samples samples, we count up to max_samples with sample_count and use that for the denominator. While we have not yet reached max_samples we don't subtract the avg when adding new_value.

The algorithm is very simple. Choosing the right types is not quite so easy. Especially when done generically.

Concerns:

  • Signedness
  • Narrowing
  • Other unwanted implicit conversions
  • Overflow --- not covered in the demo code in main
  • Really small types like unsigned char -- untested
  • the static_cast which is required to silence some Type combinations, eg Value/Sum=float and Count=int, but might be hiding other problems
  • Use of operator(). Originally I had a sample(Value new_value) member function

Compiled with

clang++-13 -std=c++20 -O3 -Wall -Wextra -Wpedantic -Wconversion -Wshadow -Wextra-semi -Werror

and that is error free. Tried to provide sensible defaults for the Sum and Count types, but allowed them to be customised.

#include <concepts>
#include <cstddef>
#include <iostream>
#include <type_traits>
#include <typeinfo>

template <typename Value, typename Sum = Value,
          typename Count = std::conditional_t<std::is_signed_v<Value>, int, unsigned>>
requires std::floating_point<Value> || std::integral<Value>
struct averager {
    Sum   sum{};
    Value avg{};

    Count       sample_count = 0;
    const Count max_samples;

    explicit averager(Count max_samples_) : max_samples(max_samples_) {}

    Value operator()(Value new_value) {
        if (sample_count != max_samples) {
            sum += new_value;
            ++sample_count;
        } else {
            std::cerr << "new_value(" << typeid(new_value).name() << ") - avg("
                      << typeid(avg).name() << ") = " << new_value - avg << "("
                      << typeid(new_value - avg).name() << ") :";

            sum += new_value - avg; // correct, and well defined, even with unsigned types
        }
        // count's signedness has been matched to sum and avg
        // must accept that, eg float has fewer sf than int, on many architectures
        avg = sum / static_cast<Sum>(sample_count);
        return avg;
    }
};

int main() {
    {
        std::cerr << "\naverager<int>(3)\n";
        auto a = averager<int>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "10 => " << a(10) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(5) << "\n";
    }
    {
        std::cerr << "\naverager<long>(3)\n";
        auto a = averager<long>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "10 => " << a(10) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(5) << "\n";
    }
    {
        std::cerr << "\naverager<unsigned>(3)\n";
        auto a = averager<unsigned>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "10 => " << a(10) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(5) << "\n";
    }
    {
        std::cerr << "\naverager<std::size_t>(3)\n";
        auto a = averager<std::size_t>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "10 => " << a(10) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(5) << "\n";
    }
    {
        std::cerr << "\naverager<float>(3)\n";
        auto a = averager<float>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "0.1F => " << a(0.1F) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(0.05F) << "\n";
    }
    {
        std::cerr << "\naverager<double, double, std::size_t>(3)\n";
        auto a = averager<double, double, std::size_t>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "0.1 => " << a(0.1) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(0.05) << "\n";
    }
    {
        std::cerr << "\naverager<int>(long double)\n";
        auto a = averager<long double>(3);
        for (auto i = 0U; i != 5; ++i) std::cerr << "0.1L => " << a(0.1L) << "\n";
        for (auto i = 0U; i != 10; ++i) std::cerr << a(0.05) << "\n";
    }
    return EXIT_SUCCESS;
}
\$\endgroup\$
2
  • \$\begingroup\$ I think I have worked out what 'max_samples ' is for ,but please explain it in the question \$\endgroup\$
    – pm100
    Commented Feb 16, 2022 at 1:26
  • \$\begingroup\$ @pm100 Ok, I have done a general description of the algorithm including that point. \$\endgroup\$ Commented Feb 16, 2022 at 1:33

1 Answer 1

1
\$\begingroup\$

There's a real risk that sum could overflow if it's one of the integer types and max_samples is too large. I think the algorithm is incorrect after max_samples is reached - some good unit tests would help ensure it works. (The test program is a good start towards that, but requires manual inspection of output).

There's a way to compute a running mean without overflow and with minimal round-off error, by not storing the sum - just count and mean. From those, the total can be inferred, and we update the mean by linear interpolation between current mean and the added value (moving mean 1/count of the way towards the value - and updating count of course). For that, I would store mean as std::common_type_t<Value, double>.

\$\endgroup\$
7
  • \$\begingroup\$ For working code using this principle, see my review request: Compute mean and variance, incrementally. \$\endgroup\$ Commented Feb 16, 2022 at 9:46
  • \$\begingroup\$ The question was deleted. I didn't name / describe this well enough. The intention is NOT to produce an accurate arithmetic mean on a running basis. But to produce a "smoothed value" which follows a "noisy signal" without using storage. The algorithm is correct for that. It follows exponential decay type maths. I will repost the question with better names / description. I would like to re-delete this one, which was already deleted before any answers came. Can you re-delete it please. As it is, it's just confusing. \$\endgroup\$ Commented Feb 16, 2022 at 9:56
  • \$\begingroup\$ No response? I studied your stats bag. It's nice, but it's not the same. RollingStatsBag comes the closest to what I intend here, but it's different because it uses storage (a std::deque). My code should run on uC where a large "array" of any sort is not feasible. It should also work with integer types only, including tiny, single byte types. In fact, the algorithm I (believe correctly) implemented is implemented in the PIC series of 8-bit micros in hardware. It's not an arithmetic mean, but it does a very good job of smoothing a noisy value with exponential decay / time constant maths. \$\endgroup\$ Commented Feb 16, 2022 at 10:26
  • 1
    \$\begingroup\$ Could it be made less confusing by re-writing the description and title? I was disappointed to see the question disappear under me when my answer was almost complete - that's why it got reopened. I'm not sure whether it's a valuable question or not, now - please come over to the 2nd Monitor if you're able to put a case for deleting for mods to consider. (And sorry I'm in lots of meetings today; will try to look in from time to time). \$\endgroup\$ Commented Feb 16, 2022 at 12:46
  • 1
    \$\begingroup\$ It seems perhaps not that many people are aware of this algorithm - it matters in embedded, and it's also useful as a high speed "damper on noisy stats" in other settings (Frame rate displays, or wifi signal strength would be a classic applications). No allocations, so very lightweight and fast. So I will post the new code with full unit tests across a wide range of types in a new code review. \$\endgroup\$ Commented Feb 16, 2022 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.