c++ - 对 double 的小数部分求和并在 "overflows"时递增的最有效方法是什么？

Question

长话短说，我有一段已有十多年历史的代码，我们和外部客户都在使用它。我们有一个“移位”数，我们可以通过它移动一个移位窗口。它被设计为一个整数，因为我们要遍历数据中的不同位置，所以没有小数移动的概念。现在，他们希望能够有一个非整数的移位数。不是插值，而是简单地让程序进行整数移位，但当我们通过该边界时让它再移位一点。

举个例子可能更有意义。假设我们有 10 个类次。职位将如下所示:0、10、20、30、40 等

现在，我们希望能够将偏移设置为 10.4。因此，我们希望转变工作如下:0、10、20、31、41 等

10.5 的偏移会变成 0、10、21、31、42 等等。

基本上，我们对那个小数位求和，当它越过小数点时，我们就再移动一位。当然，正如浮点运算经常发生的那样，我们遇到了潜在的准确性问题，但我们也希望保持速度。一种天真的方法是在开始时将小数位分开并继续对其求和，检查它的值并在它达到 1.0 时递减它。这样做的好处是可以遵循我对操作的看法，但它涉及每次迭代的条件检查，并且通常有可能出现累积错误。

我还可以看到预先计算我们可以添加多少次小数位，然后我们必须检查它是否超过 1.0(所以如果我们的小数位是 0.5，我们知道我们只需要每隔一次检查一次. 或者如果它是 0.3，我们知道我们只需要每四个左右检查一次)。

处理重复求和的通常方法当然是用乘法代替它，但在这里，我们不太关心实际的总和，而是预测哪些帧需要“再移动一个”使事情在最后匹配。

我们的典型任务涉及此类对相对较小的因素组合进行操作，例如以 96.46875 的偏移迭代少于 3000 次。但是，无法保证此约束将保持有效，因此我被告知要考虑到有人将窗口移动一千万次的可能性，而我们仍然想知道要移动多远。

有什么建议吗？

Answer 1

考虑将 shift 设置为最接近所需值的两倍，并通过以下方式稍微增加(仅一次):

shift = nexttoward(shift, INFINITY); // Ensure shift is above the threshold.

然后，要计算当前位置，请使用:

result = floor(step * shift);

当 step 和 shift 的误差接近一时，这可能会产生太大的值。 (乘法本身也可能存在轻微的舍入误差。)但是，很多步骤都不会出现这种情况，如下所示。

shift 中的误差最多为 1.5 ULP(从十进制初始转换为 0.5 ULP，从 nexttoward 为 1)。如果 shift 小于 1024，则 ULP 小于 2^10–52。如果 step 最多为 10,000,000，则误差小于 10,000,000 • 1.5 • 2^10–52，大约为 3.41•10^–6。因此，距离产生错误结果所需的量级还有很长的路要走。

如果您每次都通过添加 shift 来累积计算结果，而不是通过新的乘法，那么可能会出现额外的错误。这些可能仍然太小而不会导致错误，但应该对其进行评估。

如果达到上述限制，可以通过多种方式进一步减少错误。