给定一个正的增量 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+y是x和y的精确数学和,x
是浮点格式下的x,x+y
是在浮点操作中添加x
和y
的结果。此外,我将在C++中使用Float
作为浮点类型。
给定一个浮点数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超过
xm时,
x+y
会产生比
x更大的结果,这意味着
y超过了从
x到
x1的距离的一半。请注意,从
x到
x1的距离是
x
有效数字的低位中的数字1。
在二进制浮点格式中,有效数字有
p位,在低位上的位置值是高位上位置值的2
1−p倍。例如,如果
x是2
e,则其有效数字中最高位代表2
e,最低位代表2
e+1−p。
问题是给定一个
y,最小的
x是多少,使得
x+y
不产生大于
x的结果?这是使
y不超过
x
的有效数字的低位值的一半的最小
x。
假设2
e是
x有效数字的高位的位置值。那么
y ≤ ½•2
e+1−p = 2
e−p,因此
y•2
p ≤ 2
e。
因此,给定一些正数
y,最小的
x是指满足
x+y
不产生大于
x的结果的
x,其主导位2
e等于或超过
y•2
p。实际上,它必须恰好为2
e,因为所有其他浮点数,其主导位的位置值为2
e,在其有效数字中设置了其他位,因此它们更大。 2
e是主导位表示2
e的最小数字。
因此,
x是最小的2的幂,其等于或超过
y•2
p。
在C++中,
std::numeric_limits::epsilon()
(来自于头文件
<limits>
)是从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>
头文件)从浮点表示中提取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是问题所寻找的数字。
std::numeric_limits
以确定它是否有可供使用的内容? - Some programmer dudefloat
行为像一个int
。如果是这样,答案很简单:使用int
。 - Pete Beckerint
(带有10倍乘数)。 - Lightness Races in Orbit