BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ yegle (一阁|博学之人|奇峰怪石,秀山丽水) 于 (Sat May 24 19:15:02 2008) 提到: 原文地址：http://www.matrix67.com/blog/archives/362 Quake III公开源码后，有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍： 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 = 0×5f3759df - ( 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/common/cm_trace.c中也出现了这样一段解释sqrt(x)的函数，与上面的代码唯一不同的就是这个函数返回的是number*y： /* ================ SquareRootFloat ================ */ float SquareRootFloat(float number) { long i; float x, y; const float f = 1.5F; x = number * 0.5F; y = number; i = * ( long * ) &y; i = 0×5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( f - ( x * y * y ) ); y = y * ( f - ( x * y * y ) ); return number * y; } 这样的代码速度肯定飞快，我就不用多说了；但算法的原理是什么呢？其实说穿了也不是很神，程序首先猜测了一个接近1/sqrt(number)的值，然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 - a = 0的一个正实根，它的导数是-2/x^3。运用牛顿迭代公式x' = x - f(x)/f'(x)，式子化简为x' = x * (1.5 - 0.5a * x^2)。迭代几次后，x的值将趋于1/sqrt(a)。但这段代码真正牛B的是那个神秘的0×5f3759df，因为0×5f3759df - (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的，只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事，很少有人说得清楚。这篇论文比较科学地解释了这个常数。 ☆─────────────────────────────────────☆ purevirtual (天之健) 于 (Sat May 24 19:35:48 2008) 提到: great algorithm... 【在 yegle (一阁|博学之人|奇峰怪石,秀山丽水) 的大作中提到: 】 : 原文地址：http://www.matrix67.com/blog/archives/362 : Quake III公开源码后，有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍： : float Q_rsqrt( float number ) : ................... ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Sat May 24 19:44:35 2008) 提到: yegle很龌龊，乱转帖。人家原文，最后一句的开头，这篇论文，是个链接。我说怎么看了这个文章，也没发现它如何解释了这个常数…… ☆─────────────────────────────────────☆ yegle (一阁|博学之人|奇峰怪石,秀山丽水) 于 (Sat May 24 19:49:19 2008) 提到: 所以我在帖子开头给了原文链接，zt…… 【在 ericyosho (ericyosho) 的大作中提到: 】 : yegle很龌龊，乱转帖。 : 人家原文，最后一句的开头，这篇论文，是个链接。 : 我说怎么看了这个文章，也没发现它如何解释了这个常数…… : ................... ☆─────────────────────────────────────☆ Goldfather (Mike|godfather) 于 (Sat May 24 19:50:26 2008) 提到: zt 好好准备今晚演讲吧，vi我很不熟的。。。【在 yegle (一阁|博学之人|奇峰怪石,秀山丽水) 的大作中提到: 】 : 所以我在帖子开头给了原文链接，zt…… ☆─────────────────────────────────────☆ yegle (一阁|博学之人|奇峰怪石,秀山丽水) 于 (Sat May 24 19:51:36 2008) 提到: 啊啊啊啊……我忘了今晚的活动…… 【在 Goldfather (Mike|godfather) 的大作中提到: 】 : zt : 好好准备今晚演讲吧，vi我很不熟的。。。 ☆─────────────────────────────────────☆ purevirtual (天之健) 于 (Sat May 24 19:52:38 2008) 提到: big zt 【在 yegle (一阁|博学之人|奇峰怪石,秀山丽水) 的大作中提到: 】 : 啊啊啊啊……我忘了今晚的活动…… ☆─────────────────────────────────────☆ yegle (一阁|博学之人|奇峰怪石,秀山丽水) 于 (Sat May 24 19:53:16 2008) 提到: 幸好我不是主讲…… 【在 purevirtual (天之健) 的大作中提到: 】 : big zt ☆─────────────────────────────────────☆ windam (棒棒糖) 于 (Sat May 24 20:22:28 2008) 提到: i = 0×5f3759df - ( i >> 1 ); // what the fuck? 赞注释…… = = 第一次看到这个函数的时候，实在是被carmark的代码雷到了…… ☆─────────────────────────────────────☆ PtwCJ (鲜的每日C|头像不是我，我是长毛贼~~) 于 (Sat May 24 22:23:31 2008) 提到: 配合注释的话，题目应该改为操蛋的0x5f.... 那篇论文谁看完了？我看到后面大片的公式就放弃了...... ☆─────────────────────────────────────☆ mayao11 (卡马克的fans) 于 (Sat May 24 23:54:22 2008) 提到: 知道很nb，但是看不下去…… 【在 PtwCJ 的大作中提到: 】 : 配合注释的话，题目应该改为操蛋的0x5f.... : 那篇论文谁看完了？我看到后面大片的公式就放弃了...... ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Sun May 25 00:52:00 2008) 提到: 管他怎么的，反正就是利用了double和int型不一样的存储结构就是了。又一次指针的完胜，又一次恐怖的完败。我领教了指针的威力，也更加敬而远之了。 ☆─────────────────────────────────────☆ coolfantasy (Cool) 于 (Sun May 25 14:11:09 2008) 提到: 卡马克密码吧 ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Sun May 25 14:12:19 2008) 提到: 这就是所谓的magic number吧。

[合集] [zz]神秘的0×5f3759df 不可思议的Quake III源码