全部博文(58)
分类: WINDOWS
2008-12-26 17:53:25
文章标题:Representation of Integers and Reals II 原 作 者:By misof 原 出 处:农夫三拳@seu 发 布 者:loose_went 发布类型:翻译 发布日期:2007-02-27 今日/总浏览:2/4556 传闻: 浮点数变量不仅仅可以存储数字还可以存储一些异值 零(Zero) 这里有必要注意一下如果memset()用0来对一个浮点数的数组进行填充,那么存储的数将为0。同样的,由于C++中的全局变量初始化为0的位形式,因此全局的浮点数变量也被初始化为0。 这里有关于负0的相当一部分狡猾的陷阱。例如,如果x=0.0,表达式"0.0 - x"和"-x"并不是等价的,前面表达式的值是0.0,后面则是-0.0。 我对这个问题的看法是:负0能够“制造一个学习体验的机会”,当他们像以往一样打印出"-0"或者"-0.0"(这里“学习体验”指的是你花费在学习为什么得到这些奇怪值的时间和精力)。 无穷数(Infinities) 不是一个数字(Not a Number) QNaN指的是尾数设置了最高有效位的NaN。QNaN通常出现在数学运算中。当结果在数学中没有定义时,通常产生这些QNaN值。(例如,3*sqrt(-1.0)就是一个QNaN) SNaN指的是尾数清除了最高有效位的NaN。它用来标记操作时引发的异常。SNaN可以很容易的被指派给一个未初始化的变量来捕获一些不正确的使用。 低能数(Subnormal numbers)
对所有特殊的数进行操作(Operations with all the special numbers) 所有的操作都是以直觉的方式定义的。任何有NaN参与的 操作将会产生NaN的结果。一些其他的操作见下表。(在表中,r是一个可以被表示的正数。∞是无穷大数,÷是平常的浮点数除法。)一个完整的列表可以在标准中或者你的编译器文档中查找到。注意甚至于这些值的比较操作都进行了定义。这个话题超过了本篇文章,如果你感兴趣的话,可以浏览文章末尾的参考。
传闻: 浮点数可以通过内存中的位模式进行对比 正确性: 正确 注意我们把符号比较单独分开来。如果两个数之中一个是负数,另外一个是正数,那么结果很显然。如果两个数都是负数的话,我们可以通过将符号取反,然后进行比较,最后返回相反的答案即可。从现在起,我们讨论的仅仅是非负数的比较。 当比较位模式的时候,前面的一些位组成指数,指数越大,位模式的字典序就越靠后。类似的,具有相同指数的位模式可以通过比较它们的尾数。 另外可以考虑成这样:当比较两个以上述形式存储的非负数的时候,比较的结果总是同具有相同位模式的整数的比较一致。(注意这将使得比较相同的快) 传闻: 比较浮点数相等通常是一个坏主意 ![]() 将打印多少个星呢?10个?运行它看看,结果将是令人惊讶的。这个代码持续不断的打印星直到我们结束它。 问题在哪呢?正如我们所知道的,双精度数并不是无限精确的。我们在这里碰到的问题是这样的:在二进制中,0.1的表示并不是有限的。十进制的0.1和二进制的0.0(0011)是等价的,这里括号括住的部分是循环部分。当0.1存储在double变量中,它被近似成最近的可以表示的数。因此当我们加上10次之后,结果并不是刚刚好等于1。 最常见的建议是当比较两个双精度的数时,使用一些误差(通常用ε表示)。例如,你也许听到如下的提示:“考虑双精度数a和b相等时使用:if(fabs(a-b)<1e-7)”。注意这个只是一小步提高而不是最佳的方法。后面我们将给出一个更好的方法。 传闻: 浮点数并不准确,它们是近似的。 正确性: 部分正确 是的,如果一个数字不能够被精确的表示,那么它需要近似。但是有的时候一个比这个更重要的事实是许多重要的数字(像0, 2的幂次方,等等。)都能够被精确的存储,甚至可以做的更好。注意双精度数的尾数包含的位数要多于32位,因此int所有的二进制位都可以放到尾数中并且存储的值是精确的。 这个还可以改进。如果我们注意到2^54>10^16,很清楚任何具有15个十进制数字的整数最多具有54个二进制数字,因此它在double中进行存储时不需要近似。这个观察的结果甚至可以推广到非整数值:double能够存储任何具有最多15个十进制数字的数(在正常表示的范围)。 单精度数通过类似的计算显示他们能够仅能够存储最多7个最高有效位的十进制数。这对于实际应用来说太少了,并且最重要的是,它提供的精度要小于TC在要求返回浮点数值时所要求的精度。道理非常清楚:绝对不要使用单精度数!严重一点的说,想都不要想。现在都是有足够的可用内存了。 附带一点注意,一旦近似的错误在你的计算中出现,它们将会引起更深的计算错误。因此即使结果应该是一个整数,它在浮点数中的表示也不是一模一样的。可以想想上面打印星号的循环那个例子。 传闻: 我听说long double能提供更好的精度 80个字节的扩展双精度类型在Intel 80*87双核浮点运算中内部使用,其目的是位了能够在来来回回的位移操作中不丢失IEEE-754标准下64位(和32位)格式的精度。当g++中的优化被设置为非0值时,g++在生成代码时将在内部使用long double而不是double和single。这个扩展形式能够存储19位10进制的最高有效位。 如果你需要更加高的精度,你要么实现自己的数学运算,或者使用Java数学库中的BigInteger和BigDecimal类。 传闻: 在实际使用中,使用不同的ε值来比较浮点数没有什么区别 正确性: 错误 通常当你在包含浮点数计算的任务的SRM之后到Round Tables看看你会看到有人发出像“我把精度从1e-12改成1e-7就通过了practice room所有的系统测试”这样的消息。 这样的讨论的例子还有: , , , 和 .(它们都是值得一读的,从其他人的错误中学习要比从自己当中少痛苦一点) ![]() ![]() 这个程序将会打印多少个点呢?这次很清楚,不是吗?这次的终止条件不再是等于测试。这个循环将会在10^22遍历后停止。或者。。是吗? 真糟糕,这又一次的成了死循环。为什么会这样呢?因为当r这个值变得大了,这个变量的精度并不能够足够大的存储所有r的十进制下的数。最后一些会丢失掉。因此当我们在这么大的一个数后加1,结果又被近似到原来的数了。 练习:试着判断一下我们这个循环里r所能达到的最大值。检查你的答案,如果你的判断出错了,找出它的原因。 在作出观察之后,我们将显示为什么表达式fabs(a-b) 考虑值123456123456.1234588623046875和123456123456.1234741210937500。它们都没什么特别之处,仅仅是两个double可以在不进行近似的情况下就能存储的两个值。他们直接的差大约在2e-5. 现知让我们看看这两个值的位形式: 是这样的,没错。这是在double中可以被存储的两个连续的值。任何使用近似得到的错误都能够使得其中对一个变成另外一个(或者超过)。但是他们仍然是不一样的,因此我们原始的测试“相等”不能够工作。 我们真正需要的是容忍一些小的精度误差。正如我们所看到的,double能够近似存储最多15个10进制数字的数。通过近似积聚的精度错误,最后一些数字将会丢失。但是我们究竟应该怎样容忍这些误差呢? 我们将不使用固定常数ε,而使用一个与比较的数数量级相关的值。更确切点说,如果x是一个双精度数,那么x*1e-10是一个比x小10倍数量级的数。它的最高有效位对应于x的第11位最高有效位。这使得它能够很好的满足我们的需要。 换句话说,一个更好的方式来比较a,b两个双精度数是否“相等”就是检查a是否在b*(1-1e-10)和b*(1+1e-10)之间。(小心,如果b是负数的时候,这两个数中的第一个将会更大!) 看到用这样的比较方式的问题了吗?试着比较1e-1072和-1e1072.这两个数都机会相等并且等于0,但是我们的测试在处理这种情况时会失败。这就是为什么我们既需要做第一个测试(测试绝对误差)和第二个测试(测试相对误差)。 这就是TC中用来检查你的返回值是否正确的方法。现在你知道原因了。 有更好的比较函数(参见其中的一篇参考文章),但是更重要的是要知道在实际中你经常仅仅使用绝对误差测试而侥幸成功。为什么? 这个方法的优点很明确:检查绝对误差要比上面的高级测试简单。 作为一个有用的例子,注意如果一个整数n是平方数(也就是说,对于某个整数k,n=k^2),那么sqrt(double(n))将返回k的精确值。正如我们所知道k可以存储为与n相同类型的变量,代码 int k = int(sqrt(double(n)))是安全的,这里将不会出现近似错误。 传闻: 如果我将同样的计算做两次,那么得到的结果将相等 在C++当中,这个传闻并不总是正确。问题在于根据标准一个C++编译器有的时候能够使用一个更大的数据类型进行内部运算。并且事实上,g++有的时候内部使用long double而不是double来得到较高的精度。存储的值只有在必要时才转换类型为double。如果是由你的编译器来决定你计算实例是内部使用long double还是double,那么不同的近似将影响结果,因此最终的结果也就不一样了。 这是一个几乎无法发现的bug并且非常烦人。假设你在你计算中的每一步加入了一个调试输出,你无意中是的每一步之后中间结果都被转换成了double并且输出。换句话说,你迫使编译器在内部使用double,瞬间一切都能工作正常了。但是当你移去这些调试输出时,这个程序又开始出错了。 一种方式是写代码时仅使用long double。 作为一个例子,表达式x+y-z可能一次被看成x+(y-z),而另外一次可能变成了(x+y)-z. 试试当x=1.0,y=z=10^30的情况。 因此即使你有两段相同的代码,你也不能保证他们会有相同的结果。如果你想要这个保证的话,将这些代码封装成一个函数然后在这两种情况下调用同样的函数。 |