c - 快速整数标准偏差？

Question

很久以前，我有一个非常快的纯整数标准偏差函数(在 C 中)，它会返回“相当”准确的值，不使用除法或乘法，只是移位和加法。从那以后，我丢失了那个代码，Google 一直无法帮助我找到类似的东西，而且我的离散数学技能有点生疏，无法重新推导它。

在我的特定情况下，我有一个 14 位 ADC 值列表，我想在缺少浮点硬件的 8 位处理器上快速计算出“足够接近”的标准偏差。

这会引起任何人的注意吗？

Answer 1

根据@KerrekSB 提供的链接，我们可以重新设计算法以仅使用整数运算。

uint32_t std_var (uint16_t a[], uint16_t n) {
    if (n == 0) return 0;
    uint64_t sum = 0;
    uint64_t sq_sum = 0;
    for(unsigned i = 0; i < n; ++i) {
       uint32_t ai = a[i];
       sum += ai;
       sq_sum += ai * ai;
    }
    uint64_t N = n;
    return (N * sq_sum - sum * sum) / (N * N);
}

要获得标准偏差，请对结果求平方根。要实现整数平方根，您可以选择以下提供的众多答案之一:

• Looking for an efficient integer square root algorithm for ARM Thumb2

该算法不会尝试考虑中间计算期间的任何舍入误差，它只是假设所有值都适合，因此不需要舍入。这就是允许以直接的方式呈现公式的原因。单程方差的优化算法通常会执行中间除法，以尝试补偿由于取消引起的错误。例如(这是来自 Wikipedia ):

double std_var_stable (uint16_t a[], uint16_t n) {
    if (n == 0) return 0;
    unsigned i;
    double mean = 0;
    double M2 = 0;
    for(i = 0; i < n; ++i) {
       double delta = a[i] - mean;
       mean += delta / (i + 1);
       M2 += delta * (a[i] - mean);
    }
    return M2/n;
}

但是，中间除法对于纯整数数学算法既不合适也不理想。