执行 n 次浮点数加法或一次整数乘法哪个更好？
Is it better to perform n additions of a floating-point number or one integer multiplication?
考虑以下两种情况：
// Case 1
double val { initial_value };
for (int i { 0 }; i < n; ++i) {
val += step;
foo(val);
}
// Case 2
for (int i { 0 }; i < n; ++i) {
double val = initial_value + i * step;
foo(val);
}
其中n是步数，initial_value是类型double的某个给定值，step是类型double的某个预定值val 是函数 foo 后续调用中使用的变量。哪种情况产生的浮点错误较少？我的猜测是第二种，因为只有一次加法和乘法，而第一种情况会导致所有 n 加法的浮点表示错误。我问这个问题是因为我不知道要搜索什么。像这样的案例有没有好的参考资料？
实际上，变量 val 将用于两种情况的循环中。我没有包含任何示例，因为我只对浮点错误感兴趣。
选项 2 的误差明显较低。
多少钱？好吧，为了简单起见，我们首先假设 initial_value 为 0。您有 53 个有效位，您看到舍入错误的速度取决于我们在加法过程中能够以多快的速度设法将这些错误移出远端。
所以让我们选择 step 以便理想情况下有效位全为 1：0.999999999999999999999999.
现在舍入误差是 step 每次加法的远端的 log2(val/step) 位。第一次迭代时不多，但错误很快就会变得明显。
选择一个巨大的 initial_value 并且错误会变得非常极端。对于 initial_value >= pow(2, 53) * step，您的第一个循环甚至在迭代之间根本无法更改 val。
您的第二个循环仍能正确处理。
考虑 by supercat（强调我的）：
The point is that in many scenarios one might want a sequence of values that are uniformly spaced between specified start and end points. Using the second approach would yield values that are as uniformly spaced as possible between the start point and an end value that's near a desired one, but may not quite match.
和 by Bathsheba:
Both are flawed. You should compute the start and end, then compute each value as a function of those. The problem with the second way is you multiply the error in step. The former accumulates errors.
我建议几个备选方案。
自 C++20 起，标准库提供了 std::lerp 其中 std::lerp(a, b, t) returns “参数 t 的 a 和 b 之间的线性插值（或外推，当 t 超出 [0,1]) 范围时。
像value = (a * (n - i) + b * i) / n;这样的公式可能会导致中间值的分布更加均匀1。
(1) Here 我尝试针对不同的极端和样本点数量测试所有这些方法。该程序比较每个算法在相反方向（首先从左到右，然后从右到左）应用时生成的值。它显示了中间点的值之间的绝对差之和的平均值和方差。
其他指标可能会产生不同的结果。
考虑一个极端情况。假设 initial_value 比 step 大得多。大得多。如此之大以至于 initial_value + step == initial_value 由于浮点表示的限制。但是，我们不希望这种“极端”情况变得过于极端。给 initial_value 设置一个上限，比如说保持足够小以拥有 initial_value + (2*step) != initial_value。 （有些人可能将此称为将 step 置于某个 epsilon 和该 epsilon 的一半之间，但我会混淆术语。）现在 运行 通过您的代码。
在第一个循环中，val 将在每次迭代时等于 initial_value，因为没有执行任何会更改其值的操作。相反，如果有足够的迭代，第二个循环最终将具有不同的 val 值。因此，第二个选项，即计算 initial_value + i * step 的选项在这种极端情况下更准确。
我们还应该看看对侧肢体。假设 initial_value 相对于 step 如此之小以至于 initial_value + step == step。在这种情况下，initial_value 也可能为零，问题简化为询问是否有比 i 和 step 相乘更准确的方法来计算 i*step。 （如果有的话，我可能想要一个新的编译器。）因此，在这种极端情况下，第二种选择并不比第一种差。
极端案例分析不是定论，但往往能揭示趋势。我将计算推向了相反的极端，第二个选项从绝对好到绝对不差。我愿意得出结论，第二个选项产生的错误更少。
警告： 错误的大小可能可以忽略不计，不值得编码。此外，该问题的范围有限，忽略了其他考虑因素（例如 step 来自哪里；如果它是除以 n 的结果，可能会有更好的选择）。尽管如此，在问题提出的狭窄场景中，计算 initial_value + i*step 每次迭代看起来都是获得最小数值误差的方法。
包括<cmath>并使用std::fma(i, step, initial_value)总是会产生最好的结果，前提是i不会太大以至于将其转换为浮点型会产生舍入误差。这是因为指定 fma 产生的结果等效于计算 i•step + initial_value 的实数算术值，然后将其四舍五入为最接近的可表示值。它在乘法之后和加法之前没有内部舍入，因此它产生了可以用浮点类型表示的最佳结果。
在乘法和加法之间，通常首选乘法。加法有可能产生更好的结果。假定 IEEE-754 双精度二进制，一个示例很容易构造为 initial_value = -1./3、i = 3 和 step = 1./3。然后在 initial_value + step + step + step 中，initial_value + step 产生正好为零（因此没有舍入误差），添加 step 没有错误，第二个添加只是加倍 step，这也有没有错误。所以加法产生了没有错误的最终结果。相比之下，在initial_value + 3*step中，3*step有一个舍入误差，并且通过加法仍然存在。
但是，除了特意构建的示例之外，乘法通常会产生比加法更好的结果，这仅仅是因为它使用的运算更少，在大多数情况下要少得多。通常，重复加法中的舍入误差会像随机游走一样，有时会增加累积误差，有时会减少累积误差。随机游走有时可以 return 到原点，但很少这样做。所以很少有一个有很多加法的序列的累积误差比一个乘法和一个加法的表达式更接近原点（零误差）。
考虑以下两种情况：
// Case 1
double val { initial_value };
for (int i { 0 }; i < n; ++i) {
val += step;
foo(val);
}
// Case 2
for (int i { 0 }; i < n; ++i) {
double val = initial_value + i * step;
foo(val);
}
其中n是步数，initial_value是类型double的某个给定值，step是类型double的某个预定值val 是函数 foo 后续调用中使用的变量。哪种情况产生的浮点错误较少？我的猜测是第二种，因为只有一次加法和乘法，而第一种情况会导致所有 n 加法的浮点表示错误。我问这个问题是因为我不知道要搜索什么。像这样的案例有没有好的参考资料？
实际上，变量 val 将用于两种情况的循环中。我没有包含任何示例，因为我只对浮点错误感兴趣。
选项 2 的误差明显较低。
多少钱？好吧，为了简单起见，我们首先假设 initial_value 为 0。您有 53 个有效位，您看到舍入错误的速度取决于我们在加法过程中能够以多快的速度设法将这些错误移出远端。
所以让我们选择 step 以便理想情况下有效位全为 1：0.999999999999999999999999.
现在舍入误差是 step 每次加法的远端的 log2(val/step) 位。第一次迭代时不多，但错误很快就会变得明显。
选择一个巨大的 initial_value 并且错误会变得非常极端。对于 initial_value >= pow(2, 53) * step，您的第一个循环甚至在迭代之间根本无法更改 val。
您的第二个循环仍能正确处理。
考虑
The point is that in many scenarios one might want a sequence of values that are uniformly spaced between specified start and end points. Using the second approach would yield values that are as uniformly spaced as possible between the start point and an end value that's near a desired one, but may not quite match.
和
Both are flawed. You should compute the start and end, then compute each value as a function of those. The problem with the second way is you multiply the error in step. The former accumulates errors.
我建议几个备选方案。
自 C++20 起，标准库提供了 std::lerp 其中
std::lerp(a, b, t)returns “参数 t 的 a 和 b 之间的线性插值（或外推，当 t 超出 [0,1]) 范围时。像
value = (a * (n - i) + b * i) / n;这样的公式可能会导致中间值的分布更加均匀1。
(1) Here 我尝试针对不同的极端和样本点数量测试所有这些方法。该程序比较每个算法在相反方向（首先从左到右，然后从右到左）应用时生成的值。它显示了中间点的值之间的绝对差之和的平均值和方差。
其他指标可能会产生不同的结果。
考虑一个极端情况。假设 initial_value 比 step 大得多。大得多。如此之大以至于 initial_value + step == initial_value 由于浮点表示的限制。但是，我们不希望这种“极端”情况变得过于极端。给 initial_value 设置一个上限，比如说保持足够小以拥有 initial_value + (2*step) != initial_value。 （有些人可能将此称为将 step 置于某个 epsilon 和该 epsilon 的一半之间，但我会混淆术语。）现在 运行 通过您的代码。
在第一个循环中，val 将在每次迭代时等于 initial_value，因为没有执行任何会更改其值的操作。相反，如果有足够的迭代，第二个循环最终将具有不同的 val 值。因此，第二个选项，即计算 initial_value + i * step 的选项在这种极端情况下更准确。
我们还应该看看对侧肢体。假设 initial_value 相对于 step 如此之小以至于 initial_value + step == step。在这种情况下，initial_value 也可能为零，问题简化为询问是否有比 i 和 step 相乘更准确的方法来计算 i*step。 （如果有的话，我可能想要一个新的编译器。）因此，在这种极端情况下，第二种选择并不比第一种差。
极端案例分析不是定论，但往往能揭示趋势。我将计算推向了相反的极端，第二个选项从绝对好到绝对不差。我愿意得出结论，第二个选项产生的错误更少。
警告： 错误的大小可能可以忽略不计，不值得编码。此外，该问题的范围有限，忽略了其他考虑因素（例如 step 来自哪里；如果它是除以 n 的结果，可能会有更好的选择）。尽管如此，在问题提出的狭窄场景中，计算 initial_value + i*step 每次迭代看起来都是获得最小数值误差的方法。
包括<cmath>并使用std::fma(i, step, initial_value)总是会产生最好的结果，前提是i不会太大以至于将其转换为浮点型会产生舍入误差。这是因为指定 fma 产生的结果等效于计算 i•step + initial_value 的实数算术值，然后将其四舍五入为最接近的可表示值。它在乘法之后和加法之前没有内部舍入，因此它产生了可以用浮点类型表示的最佳结果。
在乘法和加法之间，通常首选乘法。加法有可能产生更好的结果。假定 IEEE-754 双精度二进制，一个示例很容易构造为 initial_value = -1./3、i = 3 和 step = 1./3。然后在 initial_value + step + step + step 中，initial_value + step 产生正好为零（因此没有舍入误差），添加 step 没有错误，第二个添加只是加倍 step，这也有没有错误。所以加法产生了没有错误的最终结果。相比之下，在initial_value + 3*step中，3*step有一个舍入误差，并且通过加法仍然存在。
但是，除了特意构建的示例之外，乘法通常会产生比加法更好的结果，这仅仅是因为它使用的运算更少，在大多数情况下要少得多。通常，重复加法中的舍入误差会像随机游走一样，有时会增加累积误差，有时会减少累积误差。随机游走有时可以 return 到原点，但很少这样做。所以很少有一个有很多加法的序列的累积误差比一个乘法和一个加法的表达式更接近原点（零误差）。