javascript - 用JavaScript添加一堆 float ，总和的错误是什么？

Question

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

在一个简单的脚本中，我添加了一堆浮点数并比较总和。我注意到有时结果不正确（两个应该相等的总和不正确）。我在数值分析方面相当虚弱，但是即使在回顾了Is floating point math broken?和What Every Computer Scientist Should Know About Floating-Point Arithmetic和Comparing Floating Point Numbers, 2012 Edition之后，我仍然对如何最好地比较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。精确舍入运算的中间结果仍被舍入，这仍然可能导致错误。

机器epsilon有多大？ 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 *机器epsilon *绝对值的和限制），但同时指出，如果该和以IEEE双精度格式进行，则机器epsilon为大约1e-16，因此对于任何合理的n值，n *机器epsilon都将远小于1（n远小于1e16）。如何使用此错误界限检查两个浮点和是否相等？如果总和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，它是以2为底的1/2 ULP？

如果两个浮点和相等，则它们的绝对差必须小于误差范围的两倍，以2为底的ULP为1？因此在JavaScript中，Math.abs（a-b）
Comparing Floating Point Numbers, 2012 Edition描述了另一种基于相对误差的比较浮点数的技术。在JavaScript中，是否可以找到两个浮点数之间可表示数字的数量？

Answer 1

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

JavaScript由ECMA Language Specification指定，该JavaScript表示使用IEEE-754 64位二进制浮点，并且使用“舍入至最近”模式。我看不到任何规定像某些语言一样允许额外的精度。

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

当运算的确切数学结果是y，并且没有溢出时，则采用舍入至最近模式的IEEE-754二进制浮点数中的最大误差为1/2 ULP（y），其中ULP（y）是大小上恰好高于和低于y的两个可表示值之间的距离（如果y可以精确表示，则将y本身用作“上方”值）。这是最大的误差，因为y总是恰好在两个边界值之间的中点，或者在一侧或另一侧，所以从y到边界值之一的距离最多是从中点到边界值的距离。

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

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

在这一点上，加法可能会四舍五入，因此到目前为止，部分和可能略大于3b，而下一个和可能会略大于4b。如果要计算错误的严格界限，可以使用以下算法：

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

也就是说，对于将要执行的每个加法，在给定的实际值加上所有先前的误差的情况下，添加一个误差范围，该误差范围是最大可能结果的ULP的1/2。 （上面的伪代码需要扩展精度或向上舍入以保持数学上的严格性。）

因此，仅给出要添加的数字的数量及其大小的界限，我们就可以预先计算误差界限，而无需事先知道它们的具体值。该误差范围将与n2成正比。

如果此潜在错误过高，则可以通过以下方法来减少它：


不必将数字连续地相加，而是可以将它们分成两半，并且可以将两半的和相加。每个部分都可以这种方式递归求和。完成此操作后，部分和的最大量将较小，因此其误差的范围将较小。例如，连续相加1，我们得到的总和为2、3、4、5、6、7、8，但是通过这种拆分，我们得到的平行总和为2、2、2、2、4、4，然后8。
我们可以对数字进行排序，并通过添加相互抵消的数字（正负数字互补）或首先添加较小的数字来使总和较小。
可以使用Kahan summation algorithm来获得一些扩展的精度，而无需付出额外的努力。




考虑一种特殊情况：

考虑将n个非负数相加，得出计算出的总和s。则s中的误差最多为（n-1）/ 2•ULP（s）。

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