3

当我用 JavaScript 添加一堆浮点数时，总和的错误界限是什么？应该使用什么误差界限来检查两个和是否相等？

在一个简单的脚本中，我添加了一堆浮点数并比较总和。我注意到有时结果不正确（两个应该相等的总和不正确）。我在数值分析方面相当薄弱，但即使在复习之后浮点数学被破坏了吗？和What Every Computer Scientist Should Know About Floating-Point Arithmetic and Comparing Floating Point Numbers，2012 版我对如何最好地比较 JavaScript 中的浮点和感到困惑。

首先，我很困惑：IEEE 标准要求加法、减法、乘法和除法的结果必须精确四舍五入（就好像它们被精确计算然后四舍五入到最接近的浮点数一样）。如果 JavaScript 基于 IEEE 标准，0.1 + 0.2 != 0.3 怎么可能？

我想我自己回答了这个问题：我更容易考虑以 10 为底的示例。如果 1/3 近似为 0.333...333，2/3 近似为 0.666...667，则 1/3 + 1/ 3 = 0.666...666 完全四舍五入（它是两个近似值的精确总和）但 != 0.666...667。精确舍入运算的中间结果仍然是舍入的，这仍然会引入错误。

机器ε有多大？JavaScript 浮点数显然是 64 位的，显然 IEEE 双精度格式机器 epsilon 大约是 1e-16？

当我添加一堆 (n) 浮点数（朴素求和，没有成对或 Kahan 求和）时，总和的误差范围是多少？直观地说，它与 n 成正比。我能想到的最坏情况示例（再次以 10 为底）是 2/3 - 1/3 - 1/3 + 2/3 - 1/3 - 1/3 + 等。我认为每次迭代都会增加错误1 个 ULP 的项，而总和仍然为零，所以误差项和相对误差都会无限制地增长？

在“求和中的错误”部分中，Goldberg 更精确（错误项由 n * machine epsilon * sum of the absolute values）界定，但也指出如果求和以 IEEE 双精度格式进行，则机器 epsilon 为大约为 1e-16，因此对于任何合理的 n 值（n 远小于 1e16），n * machine epsilon 将远小于 1。这个错误界限如何用于检查两个浮点和是否相等？如果它们相等，那么和 1、1e-16、n 等之间的什么关系必须为真？

另一种直觉：如果一堆数字都是正数（我的都是正数），那么尽管误差项可以无限增长，但相对误差不会，因为总和必须同时增长。在以 10 为基数的情况下，我能想到的最坏情况示例（其中误差项增长最快而总和增长最慢）是 1.000...005 是否近似为 1.000...000。重复添加此数字将使误差项增加 1/2 ULP（被加数的 0.000...005），同时将总和增加 1 个第一位单位。最差的相对误差是 4.5 ULP（0.000...045，当总和为 9.000...000），即 (base - 1) / 2 ULP，即 1/2 ULP in base 2？

如果两个浮点和相等，那么它们的绝对差必须小于误差界限的两倍，即 1 ULP in base 2？所以在 JavaScript 中，Math.abs(a - b) < a * 1e-16 + b * 1e-16？

Comparing Floating Point Numbers, 2012 Edition描述了另一种比较浮点数的技术，同样基于相对误差。在 JavaScript 中，是否可以找到两个浮点数之间的可表示数字的数量？

4

1 回答 1

3

连续相加的n 个数字之和的最大可能误差与n 2成正比，而不是与n成正比。

造成这种情况的关键原因是，每次加法都可能有一些与其总和成正比的误差，并且随着更多加法的增加，这些总和会不断增长。在最坏的情况下，总和与n成比例增长（如果将n x加在一起，则得到nx）。因此，最后，有n 个和与n成比例增长，产生与n 2成比例的总可能误差。

JavaScript 由ECMA Language Specification指定，它表示使用 IEEE-754 64 位二进制浮点并使用舍入到最近模式。我没有看到任何规定允许像某些语言那样提供额外的精度。

假设所有数字最多具有大小b，其中b是一些可表示的值。如果您的数字具有可以更具体地表征的分布，则可能会得出比下面描述的更严格的错误界限。

当运算的精确数学结果为y且没有溢出时，IEEE-754 二进制浮点与最近舍入模式的最大误差为 1/2 ULP( y )，其中 ULP( y )是y正上方和下方的两个可表示值之间的距离（如果完全可表示，则使用y本身作为“上方”值）。这是最大误差，因为y始终要么恰好位于两个边界值之间的中点，要么位于一侧或另一侧，因此从y到其中一个边界值的距离至多是从中点到边界值的距离.

（在 IEEE-754 64 位二进制中，大小小于 2 -1022的所有数字的 ULP为 2 -1074。所有 2 的较大幂的 ULP 是该数字的 2 -52倍；例如，2 -52表示 1 . 非二的幂的 ULP 是小于数字的二的最大幂的 ULP，例如，对于大于 1 和小于 2 的任何数，2 -52 。）

当一个系列中的前两个数字相加时，精确结果最多为 2 b，因此第一次相加的误差最多为 1/2 ULP(2 b )。当第三个数相加时，结果最多为 3 b，所以这次相加的误差最多为 1/2 ULP(3 b )。到目前为止，总误差最多为 1/2 (ULP(2 b ) + ULP(3 b ))。

此时，加法可能会四舍五入，因此到目前为止的部分总和可能略大于 3 b，下一个总和可能略大于 4 b。如果我们想计算误差的严格界限，我们可以使用如下算法：

Let bound = 0.
For i = 2 to n:
    bound += 1/2 ULP(i*b + bound).

也就是说，对于将要执行的每个添加，添加一个错误界限，它是给定实际添加的值加上所有先前错误的最大可能结果的 ULP 的 1/2。（上面的伪代码需要实现扩展精度或向上舍入以保持数学严谨性。）

因此，仅给定要添加的数字的数量及其大小的界限，我们可以预先计算误差界限，而无需事先知道它们的具体值。该误差界限将与n 2成比例增长。

如果这个潜在的错误太高，有办法减少它：

  • 可以将它们分成两半，然后将两半的总和相加，而不是连续添加数字。可以以这种方式对每一半进行递归求和。这样做时，部分和的最大值会更小，因此它们的误差范围会更小。例如，连续加 1，我们得到总和 2、3、4、5、6、7、8，但是，通过这种拆分，我们得到 2、2、2、2 的平行总和，然后是 4、4，然后8.
  • 我们可以通过添加相互抵消的数字（互补的正数和负数）或先添加较小的数字来对数字进行排序并保持总和更小。
  • 可以使用Kahan 求和算法来获得一些扩展的精度，而无需付出太多额外的努力。

考虑一种特殊情况：

考虑添加n 个非负数，生成计算总和s。那么s中的误差最多为 ( n -1)/2 • ULP( s )。

证明：每次加法误差最大为 1/2 ULP( x )，其中x为计算值。由于我们添加的是非负值，因此累加和永远不会减少，所以它永远不会超过s，并且它的 ULP 最多是s的 ULP 。所以n -1 次加法最多产生n -1 个 ULP( s )/2 的误差。

于 2013-11-10T22:40:20.503 回答