这会累积多少浮点错误？

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开始变大时,该方法需要在每次概率更新时读取整个计数向量,这由于高速缓存未命中和存储器访问成本而是不期望的.我设计了另一个解决方案,在我的有限测试中,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矢量,还包括其他内容)修改其决策.由于这些值不仅可以使用,而且也可以在一次迭代中多次使用,我猜想最好先计算一次然后再使用它,这就是我在更新函数中所做的.

另外,我想补充说,无论是否需要prob在每次迭代时更新向量,这都是一个非问题.该函数的合同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

现在，我强制除数以确保存在一致的舍入误差。我猜测输入数据分布的性质对于确定会累积多少错误至关重要；尽管我从来没有接触过或忘记了得出答案所需的数学知识。通过根据编译器选项了解浮点数学的确切行为，应该可以根据输入数据得出错误范围。