查找浮点计数器的最大值

Question

很抱歉，如果之前有人问过这个问题，但我找不到。

我想知道是否有一种方法可以计算用作计数器的单精度浮点数将达到 'maximum' 的点（它不再能够由于精度损失，添加另一个值）。

例如，如果我不断地把0.1f加到一个float上，我最终会到达一个值不变的点：

const float INCREMENT = 0.1f;
float value = INCREMENT;
float prevVal = 0.0f;

do {
  prevVal = value;
  value += INCREMENT;
} while (value != prevVal);

cout << value << endl;

在 GCC 上输出 2.09715e+06

有没有办法针对 INCREMENT 的不同值进行数学计算？我认为理论上应该是 float 的指数部分需要移位超过 23 位，导致丢失尾数并简单地加 0。

Answer 1

是的，这是可能的。有 std::numeric_limits::epsilon() 定义可以增加值 1.0.

的最小值

使用这个你可以计算任何数字的这个限制。

在C中有DBL_EPSILON

所以在你的情况下是这样的：

template<class T>
auto maximumWhenAdding(T delta) -> T
{
    static_assert(std::is_floating_point_v<T>, "Works only for floating points.");
    int power2= std::ilogb(delta);
    float roudedDelta = ldexp(T { 1.0 }, power2);
    if (roudedDelta != delta) {
        roudedDelta *= 2;
    }

    return 2 * roudedDelta / std::numeric_limits<T>::epsilon();
}

live example C++

注意在live test examples中delta增加失败maxForDelta，但减法成功，所以这正是你需要的。

Answer 2

给定一些正数 y 作为增量，最小的 X 添加 y 不会产生大于 X 的结果是最小的幂2 不少于 y 除以 floating-point 格式的“epsilon”的一半。可以这样计算：

Float Y = y*2/std::numeric_limits<Float>::epsilon();
int e;
std::frexp(Y, &e);
Float X = std::ldexp(.5, e);
if (X < Y) X *= 2;

证明如下。我假设使用 round-to-nearest-ties-to-even.

的 IEEE-754 二进制 floating-point 算法

在 IEEE-754 floating-point 算法中将两个数字相加时，结果是在选定方向上四舍五入到最接近的可表示值的精确数学结果。

关于符号的说明：source code format 中的文本表示 floating-point 值和操作。其他文本是数学的。所以 x+y 是 x 和 y[= 的精确数学和191=]、x是floating-point格式的x，x+y是x和[=14=相加的结果] 在 floating-point 操作中。此外，我将使用 Float 作为 C++ 中的 floating-point 类型。

给定一个 floating-point 数字 x，考虑使用 floating-point 算法添加一个正值 y，x+y。什么情况下结果会超过x?

令 x₁ 是下一个大于 x 的值，可在 floating-point 格式，设 x_m 为 x 和 之间的中点x₁。如果x+y的数学值小于x_m，然后 floating-point 计算 x+y 向下舍入，所以它产生 x。如果x+y大于x_m,它要么四舍五入并产生 x₁，要么产生更大的数字，因为 y 足够大将总和移到 x₁ 之外。如果x+y等于x_m，结果是 x 或 x₁ 中的一个甚至更低的数字。由于我们将看到的原因，在与此问题相关的情况下，这总是 x，因此计算向下舍入。

因此，当且仅当 x+y 时，x+y 产生的结果大于 x 超过x_m，意思是y超过[=77的一半距离=]x 到 x₁。注意从x到x₁的距离就是低位1的值x.

的有效数字

二进制floating-point格式，尾数为p位，低位的位置值为2^1−p乘以高位的位置值。例如，如果x为2^e，则其尾数的最高位表示2^e，最低位代表2^e+1−p.

问题是，给定一个 y，x+y 不产生结果的最小 x 是多少大于 x？ x是y不超过x的尾数低位值一半的最小x.

设2^e为x[=191=的尾数高位的位置值].则 y ≤ ½•2^e+1−p = 2^e−p, 所以y• 2^p ≤ 2^e.

因此，给定一些正数 y，至少 x x+y 不会产生大于 x有其前导位，2^e，等于或超过y•2^p。事实上，它必须恰好是 2^e 因为所有其他 floating-point 前导位的位置值为 2^e 在其有效数字中设置了其他位，因此它们更大。 2^e 是前导位代表 2^{e[ 的最小数=243=].}

因此，x是等于或超过y•2^{[=77=的最小二乘方]p}.

在 C++ 中，std::numeric_limits<Float>::epsilon()（来自 <limits> header）是从 1 到下一个可表示值的步骤，这意味着它是 2^1−p。所以 y•2^p 等于 y*2/std::numeric_limits<Float>::epsilon()。（这个操作是精确的，除非它溢出到∞。）

让我们将其分配给一个变量：

Float Y = y*2/std::numeric_limits<Float>::epsilon();

我们可以通过frexp（来自<cmath> header) 从 Y 和 ldexp（也就是 <cmath>）的 floating-point 表示中提取指数，将该指数应用到新的尾数（.5 因为f frexp 和 ldexp 使用的比例）：

int e;
std::frexp(Y, &e);
Float X = std::ldexp(.5, e);

则X是2的幂，小于等于Y。它实际上是不大于 Y 的最大 2 次方，因为 2 的下一个更大的次方 2X 大于 Y。但是，我们希望两个的最小幂不小于Y。我们可以通过以下方式找到它：

if (X < Y) X *= 2;

得到的X就是问题求的数。

Answer 3

非常接近，并且是使用程序找到它的一种不错的方法（比我最初发布的那个更有效）。但是，我不一定需要程序形式的答案，只是数学形式的答案。

据我所知，答案归结为所用增量的指数和尾数位数。我们需要舍入到最接近的 2 的幂，这有点复杂。基本上，如果尾数为 0，我们什么都不做，否则我们将指数加 1。所以，假设我们现在有 delta 作为 2 的幂，表示为 1.0 x 2exp，以及 N 位的尾数，最大值值为 1.0 x 2(N + exp)。请注意，C 中的 FLT_EPSILON 等于 1.0 x 2-N。所以我们也可以通过将最接近的 2 的幂除以 FLT_EPSILON.

来找到这个

对于 0.1 的增量，最接近的 2 的幂是 0.125，或 1.0 x 2-3。因此我们想要 1.0 x 2(23 + (-3)) 或 1.0 x 221 等于 2097152.

查找浮点计数器的最大值

Finding the maximum of a floating point counter

c++

floating-point

floating-accuracy