如何找到为每个 double 值产生较小输出的乘数？

Question

你如何找到最大和正的 IEEE-754 二进制 64 值 C 使得每个正的标准化二进制 64 值 A 与 [=10] 的 IEEE-754 乘积=] 小于 A?

我知道它一定接近于 0.999999...但我想找到最大的一个。

假设四舍五入到偶数。

Answer 1

由于浮点类型的性质，C 将根据 A 的值大小而变化。您可以使用 nextafter 获取小于 1 的最大值，这将是 C

的粗略值

然而，如果 A 太大或太小，A*C 可能与 A 相同。我无法从数学上证明 nextafter(1.0, 0) 会起作用对于所有可能的 A，因此我建议这样的解决方案

double largestCfor(double A)
{
    double C = nextafter(1.0, 0);
    while (C*A >= A)
        C = nextafter(C, 0);
    return C;
}

如果您想要一个适用于任何 A 的 C 值，即使 C*A 可能不是最大的可能值，您也需要检查每个指数该类型可以表示

double C = 1;
for (double A = 0x1p-1022; isfinite(A); A *= 2) // loop through all possible exponents
{
    double c = largestCfor(A);
    if (c < C) C = c;
}

我在 Ideone 上尝试了运行并得到了结果

C                 = 0.999999999999999777955395074969
nextafter(1.0, 0) = 0.999999999999999888977697537484

编辑：

0.999999999999999777955395074969 是 0x1.ffffffffffffep-1，也是 1 - DBL_EPSILON。这与上述 Sneftel 的证明一致

Answer 2

已经有一些实验方法；这是 C = 1 - ε 的证明，其中 ε 是机器 epsilon（即 1 和大于 1 的最小可表示数之间的距离）

我们当然知道 C < 1，所以尝试 C = 1 - ε/2 是有意义的，因为它是下一个小于 1 的可表示数字。（ε/2 是因为 C 在可表示数字的 [0.5, 1) 桶中。）让我们看看它是否适用于所有 A.

我将在本段中假设 1 <= A < 2。如果 A 和 AC 都在 "normal" 区域，那么指数是什么并不重要，指数 2^0 的情况也是一样的。现在，C 的选择显然适用于 A=1，所以我们剩下区域 1 < A < 2。查看 A = 1 + ε，我们看到 AC（精确值，不是四舍五入的结果）已经大于 1；对于 A = 2 - ε，我们看到它小于 2。这很重要，因为如果 AC 在 1 和 2 之间，我们知道 AC 和 round(AC) 之间的距离（即即，四舍五入到最接近的可表示值）最多为 ε/2。现在，如果 A - AC < ε/2，那么 round(AC) = A 我们不想要。（如果 A - AC = ε/2 那么它可能给定正常 FP 舍入规则的 "ties to even" 部分舍入到 A，但让我们看看我们是否可以做得更好.) 由于我们选择了 C = 1 - ε/2，因此我们可以看到 A - AC = A - A(1 - ε/2) = A * ε/2。由于它大于 ε/2（记住，A>1），它与 A 的距离足够远，可以四舍五入。

但是！我们必须检查的 A 的另一个值是可表示的最小正常值，因为 AC 在正常范围内 而不是 所以我们的 "relative distance to nearest" 规则不适用。我们发现，在那种情况下 A-AC 恰好是该区域机器 epsilon 的一半。 "Round to nearest, ties to even" 开始，产品四舍五入等于 A。博士

对 C = 1 - ε 进行同样的操作，我们看到 round(AC) < A，并且没有其他任何东西接近 A（我们最终问是否 A * ε > ε/2，当然是）。所以妙语是 C = 1-ε/2 几乎有效，但是法线和非法线之间的界限把我们搞砸了，C = 1-ε 让我们进入了终点区。

如何找到为每个 double 值产生较小输出的乘数？

How to find the multiplier that produces a smaller output for every double values?

algorithm

floating-point

double

multiplication

ieee-754

编辑：