c# - double z=x-y 是否保证 IEEE 754 float 的 z+y==x？

Question

我有一个问题可以简化为这个问题陈述:

Given a series of doubles where each is in the range [0, 1e7], modify the last element such that the sum of the numbers equals exactly a target number. The series of doubles already sums to the target number within an epsilon (1e-7), but they are not ==.

---

下面的代码可以工作，但是它保证对满足第一句中描述的要求的所有输入都工作吗？

public static double[] FixIt(double[] input, double targetDouble)
{
    var result = new double[input.Length];
    if (input.Length == 0) return result;

    double sum = 0;
    for (int i = 0; i < input.Length - 1; i++)
    {
        sum += input[i];
        result[i] = input[i];
    }

    double remainder = targetDouble - sum;
    result[result.Length - 1] = remainder;
    return result;
}

var arr1 = Enumerable.Repeat(Math.PI / 13, 13).ToArray();
var arr2 = FixIt(arr1, Math.PI);

Debug.Print(Math.PI.ToString("R")); //3.1415926535897931
Debug.Print(arr1.Sum().ToString("R")); //3.1415926535897922
Debug.Print(arr2.Sum().ToString("R")); //3.1415926535897931

这个问题的前一个版本问的是修改第一个元素，但是修改最后一个元素将问题简化为一个已知的总和和一个已知的目标，留给我们的问题是 last = target-sum 表示 sum+last == target。

(当然没有 NaN，并且对范围的限制意味着对 last 的一些限制也可能有所帮助。)

_{关于真正的问题:我们已经以各种方式多次遇到这个问题，但我们目前正在尝试做的是减少由于数值计算而出现的浮点错误线性规划求解器(Coin-OR CBC)中的不稳定性。例如，有 6 个变量，它们都必须在 [0,X] 范围内，并且变量的总和也必须是 X。由于数值不稳定，求解器偶尔会返回略微负值和总和不准确的值X. 我们已经克服了负数问题 - 现在只是试图解决总和为 X 的问题。 (是的，我们改变结果可能会违反约束，但确保这些数字总和为 X 具有更高的优先级，而其他约束则不那么重要。)}

Answer 1

z = x-y; 不保证z+y == x，找到一个z的问题并不总是有解code> 这样的 z+y == x。证明如下。

我们假设 IEEE-754 二进制浮点算法四舍五入到最接近的值，与偶数相关。使用基本的 64 位格式，但结果适用于其他格式。请注意，64 位格式使用 53 位有效数字，这意味着只能表示具有 53 个或更少有效二进制数字的数字。

考虑一个目标 x 等于 1+2⁻⁵²。设 y 为 2⁻⁵³。然后，在 z = x-y; 之后，z+y == x 的计算结果为 false。算术细节如下所示，但是:

• z = x-y; 将z设置为1，然后z+y产生1，小于x。
• 如果我们将 z 增加到下一个可表示的数字 1+2⁻⁵²，则 z+y 产生 1+2⁻⁵¹，大于x。
• 因此 z 的值不存在使 z+y == x 为真。

详细信息:

x−y 的数学结果是 1+2⁻⁵³。由于它有 54 个有效位(从 2⁰ 到 2⁻⁵³)，它是不可表示的，x-y 的计算结果必须是圆形。最接近的两个数字是 1 和 1+2⁻⁵²。 ties-to-even 规则产生前一个数字 1，因为其有效数的低位为 0，而 1+2⁻⁵² 的低位为 1。

因此 z = x-y; 将 z 设置为 1。

那么z+y的数学结果是1+2⁻⁵³。如上，这四舍五入为 1，所以 z+y 的计算结果为 1。所以 z+y == x 比较 1 和 1+2 ⁻⁵² 并产生错误。

此外，z 的任何值都不能使比较结果为真。如果我们以最小可用步长递增 z，从 1 到 1+2⁻⁵²，则 z+y 的数学和 则为 1+2⁻⁵²+2⁻⁵³。这是两个可表示数字 1+2⁻⁵² 和 1+2⁻⁵¹ 之间的中间位置。前者低位为1，后者低位为0，所以这个z+y的计算结果是1+2⁻⁵¹，当然不等于 1+2⁻⁵²。

浮点加法是弱单调的，所以没有 z 的值会产生 1+2⁻⁵² for z+y.