快速整数标准偏差？

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

然而,对于仅整数数学算法,中间划分不合适也不合适.