c++ - 这会累积多少浮点错误？

Question

我有一个随机过程，调用时返回一个介于 0 和 K-1 之间的随机数，其中 K 可能相当高。我想跟踪任何结果发生的次数，并将所有计数归一化为概率分布。我想在每次调用随机过程时都这样做，以便我对随机过程的分布估计尽可能最新。

一个天真的方法可能如下:

while ( true ) {
    int n = randomProcess();

    ++totalCount;
    ++count[n];
    update();

    do_work_with_updated_prob_vector();
}

void update() {
    for ( int i = 0; i < K; ++i )
        prob[i] = count[i] / static_cast<double>(totalCount);
}

然而，当 K 开始变大时，这种方法需要在每次概率更新时读取整个计数 vector ，由于缓存未命中和内存访问成本，这是不可取的。我设计了另一种解决方案，在我有限的测试中，K~1000 的速度提高了大约 30%。新的更新函数需要知道最后更新元素的索引:

void fastUpdate(int id) {
    if ( totalCount == 1 ) {
        prob[id] = 1.0;
        return;
    }
    double newProb = count[id] / static_cast<double>(totalCount - 1);
    double newProbSum = 1.0 + ( newProb - prob[id] );

    prob[id] = newProb;
    for ( int i = 0; i < K; ++i )
        prob[i] /= newProbSum
}

这种方法在理论上是可行的，但是我担心浮点精度误差会由于执行的不完善的归一化而累积。我还应该偶尔调用基本的 update 函数来摆脱它们吗？如果是这样，多久一次？这个误差能有多大？我对这类问题没有什么经验，我知道我不需要低估它们。

编辑:因为这似乎很重要，所以我将更好地解释我在这里所做的事情，以便我们可以更多地关注我提出的问题。我还在顶部更新了我的第一个算法，以便它显示我做得更好。

我正在编写一系列需要学习最初未知环境的 AI 算法。在这种情况下，环境是通过将所看到的近似于分布来学习的。在每次迭代中，算法将根据新数据(不仅包括更新的 prob vector ，还包括其他内容)修改其决策。由于这些值不仅会被使用，而且还可能在单次迭代中被多次使用，我猜想最好是计算一次结果然后使用它，这就是我对更新函数所做的。

此外，我想补充一点，我是否需要在每次迭代时更新 prob vector 在这里确实不是问题。 fastUpdate 函数的约定是它会进行快速更新，这就是我的问题所在。如果我不需要如此频繁地更新，我将通过不在每次迭代时调用该函数来做到这一点。因为目前我确实需要调用它，所以我正在这样做。我希望这能澄清。

Answer 1

举个例子，以这个 python 为例:

for i in range(1000000):
    x = rnd.randrange(0,10)
    intar.append(x)
    dblar.append(x/100.0)
intsum = 0
for i in intar:
    intsum += i
dblsum = 0.0
for d in dblar:
    dblsum += d
print("int: %f, dbl: %f, diff: %f" % ((intsum/100.0), dblsum, ((intsum/100.0)-dblsum)))

产量:

int: 45012.230000, dbl: 45012.200000, diff: 0.030000

现在，我强制除数以确保存在一致的舍入误差。我猜测输入数据分布的性质对于确定将累积多少错误至关重要；虽然我从来没有新的或忘记了得出答案所必需的数学。有了基于编译器选项已知的 float 学的确切行为，应该可以根据输入数据推导出误差范围。