// SPDX-License-Identifier: GPL-2.0 /* * Functions for incremental mean and variance. * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 as published by * the Free Software Foundation. * * This program is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for * more details. * * Copyright © 2022 Daniel B. Hill * * Author: Daniel B. Hill <[email protected]> * * Description: * * This is includes some incremental algorithms for mean and variance calculation * * Derived from the paper: https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf * * Create a struct and if it's the weighted variant set the w field (weight = 2^k). * * Use mean_and_variance[_weighted]_update() on the struct to update it's state. * * Use the mean_and_variance[_weighted]_get_* functions to calculate the mean and variance, some computation * is deferred to these functions for performance reasons. * * see lib/math/mean_and_variance_test.c for examples of usage. * * DO NOT access the mean and variance fields of the weighted variants directly. * DO NOT change the weight after calling update. */ #include <linux/bug.h> #include <linux/compiler.h> #include <linux/export.h> #include <linux/limits.h> #include <linux/math.h> #include <linux/math64.h> #include <linux/module.h> #include "mean_and_variance.h" u128_u u128_div(u128_u n, u64 d) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_get_mean() - get mean from @s * @s: mean and variance number of samples and their sums */ s64 mean_and_variance_get_mean(struct mean_and_variance s) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_get_variance() - get variance from @s1 * @s1: mean and variance number of samples and sums * * see linked pdf equation 12. */ u64 mean_and_variance_get_variance(struct mean_and_variance s1) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_get_stddev() - get standard deviation from @s * @s: mean and variance number of samples and their sums */ u32 mean_and_variance_get_stddev(struct mean_and_variance s) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_weighted_update() - exponentially weighted variant of mean_and_variance_update() * @s: mean and variance number of samples and their sums * @x: new value to include in the &mean_and_variance_weighted * @initted: caller must track whether this is the first use or not * @weight: ewma weight * * see linked pdf: function derived from equations 140-143 where alpha = 2^w. * values are stored bitshifted for performance and added precision. */ void mean_and_variance_weighted_update(struct mean_and_variance_weighted *s, s64 x, bool initted, u8 weight) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_weighted_get_mean() - get mean from @s * @s: mean and variance number of samples and their sums * @weight: ewma weight */ s64 mean_and_variance_weighted_get_mean(struct mean_and_variance_weighted s, u8 weight) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_weighted_get_variance() -- get variance from @s * @s: mean and variance number of samples and their sums * @weight: ewma weight */ u64 mean_and_variance_weighted_get_variance(struct mean_and_variance_weighted s, u8 weight) { … } EXPORT_SYMBOL_GPL(…); /** * mean_and_variance_weighted_get_stddev() - get standard deviation from @s * @s: mean and variance number of samples and their sums * @weight: ewma weight */ u32 mean_and_variance_weighted_get_stddev(struct mean_and_variance_weighted s, u8 weight) { … } EXPORT_SYMBOL_GPL(…); MODULE_AUTHOR(…) …; MODULE_LICENSE(…) …;
Codebase Browser
linux