c - 快速仅整数标准差？

Question

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

在我的具体情况下，我有一个 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);
}

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

• 为 ARM Thumb2 寻找有效的整数平方根算法

该算法不会尝试在中间计算期间考虑任何舍入误差，它只是假设所有值都适合，因此不需要舍入。这就是允许以直截了当的方式呈现公式的原因。单通道方差的优化算法通常执行中间除法，以试图补偿由于取消引起的错误。例如（来自维基百科）：

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;
}

但是，对于仅整数数学算法，中间除法既不合适也不可取。