主题:开平方立方简单实现中的问题
windy0will
[专家分:2300] 发布于 2010-08-08 17:50:00
先看下面那个函数:
[code=c]
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration,
// this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}[/code]
这是在网上无意发现的,这个函数有点诡秘,功能是返回1/sqrt(number) !那个常数0x5f3759df很神秘,3759df这一部分不知道怎么得到的。按照这个思路,自己写了一个类似sqrt函数的函数:
[code=c]
float ( my_sqrt )( float f )
{ /*** 假设 sizeof(float)的值是4 ***/
float y = 0.0F ,
half_f = 0.5F * f , // f的0.5倍
two_f = 2.0F * f ; // f的2.0倍
unsigned long ul = * ( unsigned long * ) &f ;
if ( f == 0.0F ) {
return 0.0F;
}else if ( f < 0.0F ) { //返回IND
ul = 0xffc00000 ;
return * ( float * ) &ul;
}
ul = ( ul & 0x7f800000 ) ? ( 0x20000000 + ((ul-0x00800000)>>1) )
: ( 0x20000000 + ((ul+0x01800000)>>1) ) ;
ul = ( ul & 0x7f800000 ) ? ( ul - 0x0063f966 ) : ( ul ) ;
y = * ( float * ) &ul;
y = ( half_f / y ) + ( 0.5F * y ) ;
y = ( half_f / y ) + ( 0.5F * y ) ;
y = ( half_f / y ) + ( 0.5F * y ) ;
y = ( half_f / y ) + ( 0.5F * y ) ;
y = ( half_f / y ) + ( 0.5F * y ) ;
return y ;
}[/code]
函数里面的y第一次的值只保证了它的指数符合开方后的值,尾数的后22位只是简单的右移一位。经过测试发现它的误差比sqrt函数的大很多:my_sqrt只能保证误差在0.1%内。下面用s,e,f分别表示float数的符号,指数,尾数(‘.’只是用来分割,每4bit用‘.’来分割,便于观察)。如浮点数
1111.1110 1001.0011 1111.0010 0000.0111,
那么s的值为 1,e的值为 111.1110 1,f的值为 001.0011 1111.0010 0000.0111
问题: 1. 怎样提高my_sqrt函数的精确性;
2. 浮点数中的IND是什么意思,和NaN有什么关系,是不是所有的IND在内存中的表
示如下:
1111.1111 1100.0000 0000.0000 0000.0000
3. float型的下溢:对于不规范的float数(它的e等于0,f不等于0;大小等于
(-1)^s * 0.f * 2^(-127) )是不是属于下溢,如下面这个float数;如果不用
特殊的方法是不是不能得到这种不符合规范的float数;
4. 溢出的问题:发生算术溢出后会产生什么后果,int型溢出和float型溢出的后
果会不会不同。
这次问题是有点多,希望高手们能尽可能的帮我分析一下。先谢谢了!!!
最后更新于:2010-08-13 15:55:00
回复列表 (共9个回复)
沙发
cgl_lgs [专家分:21040] 发布于 2010-08-08 22:27:00
1. 这是fastSQRT为的是效率而不是精度,如果想提高则只能用Double版本的。
2. IND也属于NaN,只不过NaN有一个规定:
如果是NaN,且尾数最高位为1,则代表此数被计算出来后不需要抛出异常;
如果是NaN,且尾数最高位为0(当然其它位自然会有非0的否则就不是NaN了),则代表计算出这个值的操作将会抛出一个异常:)
3. 下溢为负无穷,上溢为正无穷:)
4. int溢出是舍去高位,浮点溢出则没东西了:)
板凳
eastcowboy [专家分:25370] 发布于 2010-08-09 06:25:00
关于推导过程,这个可以在网上搜索一下。
http://www.cnblogs.com/vagerent/archive/2007/06/25/794695.html
我的数学很差,就不献丑了。
问题1:怎样提高精确性?实际上就是问怎样提高牛顿迭代法的精确性。有两种办法,一是增加迭代次数(楼主给出的代码,已经比我找的那个链接要多一次迭代了),不过这不一定十分有效。二是采用加速迭代,这个也是见仁见智,大学有一门“数学实验”的课程讲了一些简单的加速法,不过目前也有一些新的论文。采用加速迭代,如果加速效果好的话,可以让迭代次数大大减少(指达到相同的精确度)。
问题2:IND是什么意思?
这意思应该是indeterminate,模糊的。从IEEE标准的介绍来看,IND和NaN的概念似乎有重合的地方。NaN的意思是“not a number”,不是实数。INF意思是infinite,无限,实际上意思是超过了float的表示范围,溢出。
问题3:大小等于(-1)^s * 0.f * 2^(-127) )是不是属于下溢?
根据标准,FLT_MIN是大于零的最小的float值。我想,任何比这个数小、比零大的值,应该都算作下溢吧。
问题4:发生算术溢出后会产生什么后果?
这取决于你的设置。C/C++在默认情况下,都尽可能避免所有的运行时检查,这有助于提高程序的运行效率。因此,一般C/C++是不检查溢出的,包括整数的溢出和浮点数的溢出。但可以通过设置,让计算机进行这样的检查。
函数_control87(包含在float.h头文件)可以控制浮点数的操作模式。假设设置为:
_control87(_EM_INEXACT, _MCW_EM);
则除了inexact(精度损失)之外,所有的错误都会当作浮点异常(因此,上溢、下溢、除以零、非法操作等,都会产生一个浮点异常)。默认情况下,算数溢出除了无法计算得到正确结果之外,没有任何后果。但如果进行了上面这个设置,则不仅无法得到正确结果,而且会出现浮点异常。如果这个异常得不到妥善处理,其后果就像是整数除以零那样,程序会彻底停止。
3 楼
cgl_lgs [专家分:21040] 发布于 2010-08-09 16:32:00
理论上来说,增加迭代是可以提高精度的。
但实际上因为计算过程中会有很大的舍入误差,所以多次迭代必然会导致解的飘移:)
如果你真打算以后做编译器,了解这些还是很不错的:)
另给您一个非常有营养的东西:
用Intel编译器,搞一个Real*16(16字节浮点型)做各种运算:)然后反汇编调试看看:)
4 楼
windy0will [专家分:2300] 发布于 2010-08-09 17:14:00
在测试的时候,又发现了一个问题:如果把分别用sqrt和my_sqrt得到的浮点数,按下面两种方法:(已定义float f;char s1[128],s2[128])(下面讨论f的值是1.0,2.0,3.0...10000.0时);
1. float f1 = my_sqrt( f ), f2 = sqrt( f );
sprintf( s1,"%.6f",f1 ), sprintf( s2,"%.6f",f2 );
2. sprintf( s1,"%.6f",my_sqrt( f ) ), sprintf( s2,"%.6f",sqrt( f ) );
然后用int b=strcmp(s1,s2)来比较s1和s2:用方法1得到的10000个b中全部是0;用方法2得到的b大概有好几千个不是0(基本不为0)。就是在方法2中那些不为零对应的f在用方法1得到f1和f2,然后显示它们在内存中的表示,好像也差不多全都相同。(测试的部分代码上传在附件中)
我想问一下,为什么会有这样不同的结果呢?
5 楼
cgl_lgs [专家分:21040] 发布于 2010-08-09 23:02:00
[quote]在测试的时候,又发现了一个问题:如果把分别用sqrt和my_sqrt得到的浮点数,按下面两种方法:(已定义float f;char s1[128],s2[128])(下面讨论f的值是1.0,2.0,3.0...10000.0时);
1. float f1 = my_sqrt( f ), f2 = sqrt( f );
sprintf( s1,"%.6f",f1 ), sprintf( s2,"%.6f",f2 );
2. sprintf( s1,"%.6f",my_sqrt( f ) ), sprintf( s2,"%.6f",sqrt( f ) );
然后用int b=strcmp(s1,s2)来比较s1和s2:用方法1得到的10000个b中全部是0;用方法2得到的b大概有好几千个不是0(基本不为0)。就是在方法2中那些不为零对应的f在用方法1得到f1和f2,然后显示它们在内存中的表示,好像也差不多全都相同。(测试的部分代码上传在附件中)
我想问一下,为什么会有这样不同的结果呢?
[/quote]
点一下:)
不知道您还记不记得float自动升级成double的事情:)
6 楼
windy0will [专家分:2300] 发布于 2010-08-09 23:35:00
呵呵,竟没注意到sprintf函数也是属于可变参函数。不过,如果my_sqrt和sqrt的到的是同一浮点数,那么即使提升为double型也应该是一样的:)
7 楼
cgl_lgs [专家分:21040] 发布于 2010-08-09 23:54:00
不一定喔,%.6f一样不等于 %.6lf也必须一样啊:)
因为你已赋值给一个float后,与直接传给变参的内部升级是不同的。
它们走的路线不同,一个是在赋值时舍入,输出成%.6f时再舍入,而直接输出则不是喔:)
小TIPS:别光看你自己写的my_sqrt,想想系统的sqrt可是double类型的喔:)
8 楼
windy0will [专家分:2300] 发布于 2010-08-10 00:16:00
太谢谢您了!
9 楼
cgl_lgs [专家分:21040] 发布于 2010-08-10 00:29:00
呵呵,别太客气。俺会受不了滴:)
我相信大家都喜欢讨论有思考价值的问题,故来去自然积极:)
我来回复