c++ - 查找浮点计数器的最大值

Question

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

我想知道是否有一种方法可以计算用作计数器的单精度浮点数将达到“最大值”的点(由于丢失而无法再添加另一个值的点)精确)。

例如，如果我不断添加 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

鉴于一些积极的y用作增量，最小X其中添加 y不会产生大于 X 的结果是 2 的最小幂不小于 y除以浮点格式“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;

一个证明如下。我假设使用舍入到最近关系到偶数的 IEEE-754 二进制浮点算法。

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

关于符号的说明: source code format 中的文本表示浮点值和运算。其他文本是数学的。所以 x+y 是 x 和 y 的精确数学和， x是浮点格式的 x，和 x+y是加 x的结果和 y在浮点运算中。另外，我将使用 Float对于 C++ 中的浮点类型。

给定一个浮点数 x，考虑使用浮点算法添加一个正值 y， x+y .在什么条件下结果会超过x？

令 x1 为下一个大于 x 的浮点格式可表示的值，并令 xm 为 x 和 x1 之间的中点。如果x+y的数学值小于xm，则浮点计算 x+y向下舍入，所以它产生 x。如果 x+y 大于 xm，要么向上取整并产生 x1，要么产生更大的数字，因为 y 大到足以将总和移到 x1 之外。如果 x+y 等于 xm，则结果是 x 或 x1 中具有偶数低位的那个。出于我们将看到的原因，在与此问题相关的情况下，这始终为 x，因此计算会向下取整。

因此， x+y当且仅当 x+y 超过 xm 时产生大于 x 的结果，这意味着 y 超过从 x 到 x1 的距离的一半。注意x到x1的距离是 x的有效数的低位数值1 .

在有效位为 p 位的二进制浮点格式中，低位的位置值是高位位置值的 21-p 倍。例如，如果x为2e，则其有效数的最高位代表2e，最低位代表2e+1-p。

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

设2e为x的有效数的高位的位置值。那么y ≤ ½•2e+1−p = 2e−p，所以y•2p ≤ 2e。

因此，给定一些正 y，最小的 x 其中 x+y不会产生大于 x 的结果，其前导位 2e 等于或超过 y•2p。事实上，它必须正好是 2e，因为所有其他浮点数的前导位的位置值为 2e，它们的有效数中都有其他位设置，所以它们更大。 2e 是前导位表示 2e 的最小数。

因此，x 是等于或超过 y•2p 的 2 的最小幂。

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

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

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

我们可以使用 frexp找到Y的有效数的最高位所代表的位置值。 (来自 <cmath> header )从 Y 的浮点表示中提取指数和 ldexp (还有 <cmath> )将该指数应用于新的有效数( .5 因为 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 是问题寻求的数字。