c++ - 查找浮点计数器的最大值
问题描述
如果以前有人问过这个问题,我很抱歉,但我找不到。
我想知道是否有一种方法可以计算用作计数器的单精度浮点数将达到“最大值”的点(由于丢失而不再能够添加另一个值的点精确)。
例如,如果我不断地添加0.1f
到 a 中,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。
解决方案
给定一些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
是浮点格式的xx+y
,并且是浮点运算中加x
和的结果y
。另外,我将Float
用于 C++ 中的浮点类型。
给定一个浮点数x ,考虑使用浮点运算添加一个正值yx+y
, 。在什么条件下结果会超过x?
设x 1是下一个大于x的值,可以用浮点格式表示,设x m是x和x 1之间的中点。如果x + y的数学值小于x m,则浮点计算向下舍入x+y
,因此产生x。如果x + y大于x m,要么向上取整并产生x 1,要么产生更大的数字,因为y大到足以使总和超出x 1。如果x + y等于x m,则结果是x或x 1中的任何一个具有偶数低位。由于我们将看到的原因,在与此问题相关的情况下,这始终是x ,因此计算向下舍入。
因此,当且仅当x + y超过x mx+y
时,产生大于x的结果,这意味着y超过从x到x 1的距离的一半。请注意,从x到x 1的距离是 1 的有效数字低位的值。x
在其有效数中有p位的二进制浮点格式中,低位的位置值是高位位置值的 2 1−<em>p倍。例如,如果x为 2 e,则其有效数的最高位表示 2 e,最低位表示 2 e +1−<em>p。
问题是,给定一个y ,不产生大于x的结果的最小x是多少?它是y不超过 的有效数字低位值一半的最小x。x+y
x
令 2 e为x的有效数高位的位置值。那么y ≤ ½•2 e +1−<em>p = 2 e −<em>p,所以y •2 p ≤ 2 e。
因此,给定某个正的y ,不会产生大于x的结果的最小x的前导位 2 e等于或超过y •2 p。事实上,它必须正好是 2 e,因为所有其他浮点数的前导位具有位置值 2 e的其他位都设置在它们的有效位中,所以它们更大。2 e是前导位表示 2 e的最小数字。x+y
因此,x是等于或超过y •2 p的二的最小幂。
在 C++ 中,std::numeric_limits<Float>::epsilon()
(从<limits>
标题开始)是从 1 到下一个可表示值的步骤,这意味着它是 2 1−<em>p。所以y •2 p等于y*2/std::numeric_limits<Float>::epsilon()
。(这个操作是精确的,除非它溢出到 ∞。)
让我们将其分配给一个变量:
Float Y = y*2/std::numeric_limits<Float>::epsilon();
我们可以通过使用(from header) 从浮点表示中提取指数和(also )将该指数应用于新的有效位 (因为缩放并使用):frexp
<cmath>
Y
ldexp
<cmath>
.5
frexp
ldexp
int e;
std::frexp(Y, &e);
Float X = std::ldexp(.5, e);
那么X是 2 的幂,并且它小于或等于Y。它实际上是不大于Y的 2 的最大幂,因为 2 的下一个更大的幂 2 X大于Y。但是,我们希望两个不小于Y的最小幂。我们可以通过以下方式找到:
if (X < Y) X *= 2;
结果X是问题所寻求的数字。
推荐阅读
- python - Python程序无视按钮输入
- python - Twitter 情绪分析 - 删除机器人重复以获得更准确的结果
- javascript - 将php数组数据传递给js文件
- valgrind - Valgrind 在运行可执行文件之前有很长时间的停顿
- sql - 根据列构建项目数组
- php - href 中包含 php 变量,没有打开正确的位置
- java - 将成员变量设为 final 有什么好处?
- node.js - 如何在另一个流中的某个点插入流?
- java - Java:如何获得特定条件下最快任务的返回值?
- ios - 如何在特定操作表上更改 UIAlertController 上的字体颜色?