寻找浮点计数器的最大值

8

非常抱歉,如果此问题以前已经被问过,但我找不到它。

我想知道是否有一种方法来计算单精度浮点数达到“最大值”的点(由于精度损失而不能再添加另一个值的点)。

例如,如果我不断将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。

3
你是否已查看std::numeric_limits以确定它是否有可供使用的内容? - Some programmer dude
1
这似乎是在询问如何使一个 float 行为像一个 int。如果是这样,答案很简单:使用 int - Pete Becker
@Someprogrammerdude 我刚刚查看了一下,好像没有现成的解决方案,除非我漏看了。不过可能可以通过结合其成员来想出一些hackery的方法。 - Lightness Races in Orbit
1
这个问题是合法的,但在这种特定的用例中,我同意你应该使用int(带有10倍乘数)。 - Lightness Races in Orbit
在实际场景中,使用整数并简单地使用定点数学更为合理,但我很好奇是否有一种方法来确定这一点。 - CplClegg
3个回答

2

给定一个正的增量 y,最小的 X 是使得加上 y 不会产生大于 X 的结果的最小 2 的幂次方,不小于浮点格式“epsilon”的一半除以 y。可以通过以下方式计算:

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浮点算术中,当两个数字相加时,结果是精确的数学结果,四舍五入为所选方向中最接近的可表示值。

关于符号的说明:以源代码格式表示浮点值和操作的文本。其他文本是数学上的。因此,x+yxy的精确数学和,x是浮点格式下的xx+y是在浮点操作中添加xy的结果。此外,我将在C++中使用Float作为浮点类型。

给定一个浮点数x,考虑使用浮点算术添加正值y,即x+y。在什么条件下,结果会超过x

x1为浮点格式中大于x的下一个值,xmxx1之间的中点。如果x+y的数学值小于xm,则浮点计算x+y向下舍入,因此产生x。如果x+y大于xm,则它要么向上舍入并产生x1,要么产生一些更大的数字,因为y足够大以将总和移动到x1之外。如果x+y等于xm,则结果是xx1中具有偶数低位数字的任何一个。由于我们将看到的原因,在与此问题相关的情况下,这始终是x,因此计算向下舍入。

因此,当且仅当x+y超过xm时,x+y会产生比x更大的结果,这意味着y超过了从xx1的距离的一半。请注意,从xx1的距离是x有效数字的低位中的数字1。
在二进制浮点格式中,有效数字有p位,在低位上的位置值是高位上位置值的21−p倍。例如,如果x是2e,则其有效数字中最高位代表2e,最低位代表2e+1−p
问题是给定一个y,最小的x是多少,使得x+y不产生大于x的结果?这是使y不超过x的有效数字的低位值的一半的最小x
假设2ex有效数字的高位的位置值。那么y ≤ ½•2e+1−p = 2ep,因此y•2p ≤ 2e
因此,给定一些正数y,最小的x是指满足x+y不产生大于x的结果的x,其主导位2e等于或超过y•2p。实际上,它必须恰好为2e,因为所有其他浮点数,其主导位的位置值为2e,在其有效数字中设置了其他位,因此它们更大。 2e是主导位表示2e的最小数字。
因此,x是最小的2的幂,其等于或超过y•2p
在C++中,std::numeric_limits::epsilon()(来自于头文件<limits>)是从1到下一个可表示值的步长,意味着它是21-p。因此,y•2p等于y*2/std::numeric_limits<Float>::epsilon()。(除非溢出为无限大,否则此操作是精确的。)
让我们把它赋值给一个变量:
Float Y = y*2/std::numeric_limits<Float>::epsilon();

我们可以使用frexp(来自<cmath>头文件)从浮点表示中提取Y的指数,并使用ldexp(同样来自<cmath>)将该指数应用于新的尾数(.5),以此找到Y尾数中最高位所代表的位置值:

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

那么X就是2的幂,并且它小于或等于Y。实际上,它是不大于Y的最大2的幂,因为下一个更大的2的幂,2X,大于Y。但是,我们想要不小于Y的最小2的幂。我们可以使用以下方法找到这个幂:

if (X < Y) X *= 2;

结果的X是问题所寻找的数字。


那么非规范化数呢? - EOF
@EOF:Y永远不会是次正常数,因为即使y是可表示的最小正值,将其乘以2/epsilon也会产生一个正常值。而y是否是次正常数并不重要,因为它的值参与到x+y中,而不考虑它是正常还是次正常。唯一的例外情况是在计算YX时发生了溢出到无穷大的情况,这是可以接受的,因为此时最大的有限数太小了,不能成为X,所以∞是正确的答案。 - Eric Postpischil
这是一篇很好的文章,但我发现其中有些内容有点令人困惑。关于找到“Y的有效数字所表示的最高位的位置值”的部分对我来说没有意义。例如,当y0.1f时,我们最终得到一个Y1677721.6。其有效数字为5033165,指数为147X最终变成了1048576,它本质上是相同的指数(147),但有效数字为0 - CplClegg
@CplClegg: 147 是指数的编码,而不是指数本身。实际指数为 24。在有效数字中,一个比特位的位置值是如果改变了该位,数字会发生变化的量。例如,如果指数为 24,则改变有效数字的最高位将使值增加 2^24,因此其位置值为 2^24。改变有效数字的最低位将导致值增加 2^1,因此其位置值为 2^1。(请注意,就像编码了指数一样,实际的 24 位有效数字使用有效数字字段中的 23 个和从指数字段导出的 1 个进行编码。) - Eric Postpischil
是的,我提供了编码值。实际指数为20,而不是24(147-127)。此外,领先位(我假设这与最高有效位相同)会将Y的值更改2^19,而不是2^20。一个更简单的例子是Y为1.0。这具有指数0,在尾数/有效数字中切换最高有效位会添加0.5或2^-1。我哪里错了吗? - CplClegg
@CplClegg:抱歉,我看错了数字。是的,对于0.1,Y约为1,677,721.6。其最高位的值为2^20。对于1.0,其最高位的值为2^0。尾数是完整的尾数,即1.0中的s=+s•2^0——所有24位。尾数字段中的23位不是完整的尾数,只是最后的23位。尾数字段仅编码(大部分)尾数;它不是尾数。 - Eric Postpischil

0

Marek的答案非常接近,并且使用程序查找它是一个不错的方式(比我最初发布的程序更有效率)。但是,我并不一定需要以程序形式得到答案,只需要数学形式的答案。

据我所知,答案取决于使用的delta的指数和尾数位数。我们需要四舍五入到最接近的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

在 Eric 的回答发布之前,我已经写了这个。我选择了他的回答,因为它更加全面,我认为它能够深入到问题的本质。 - CplClegg

0

是的,这是可能的。 有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();
}

C++实时示例

请注意,在实时测试示例中,delta无法增加maxForDelta,但减法是成功的,所以这正是您需要的。


但是使用epsilon,他可以计算出他所需的值。 - Marek R
1
这并没有给出正确的答案。我不确定如何使用epsilon来回答我的问题,因为它只是可以添加到1.0f的最小数字,似乎与找到value += 0.1f停止工作的点无关。 - CplClegg
2
这适用于大多数数字,但不适用于小数部分为零的数字。例如,1.0f会产生偏离2的幂次方的值33554432。此外,我不清楚为什么这样做有效。 - CplClegg
2
这个答案的开头段落是错误的。epsilon是1和下一个可表示值之间的距离。这不是可以添加到1以增加它的最小值。添加大于epsilon的一半的任何数字都会产生大于1的结果。 - Eric Postpischil
@PeteBecker 这确实是这种情况。请注意,我并没有询问如何以编程方式完成此操作,尽管我很感激您的努力。简单的数学就可以了。如果您试图处理可以是_任何_值的增量,则此代码最终会变得复杂。 - CplClegg
显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接