iamapighhh的专栏    
iamapighhh的专栏
版主:iamapighhh关注:0粉丝:0



声明转帖自 http://www.douban.com/note/93460299/                    http://www.ourdev.cn/bbs/bbs_content.jsp?bbs_sn=5367145&bbs_page_no=1&search_mode=1&search_text=%CB%E3%B7%A8&bbs_id=9999 以下正文: Quake-III Arena (雷神之锤3)是90年代的经典游戏之一。该系列的游戏不但画面和内容不错,而且即使计算机配置低,也能极其流畅地运行。这要归功于它3D引擎的开发者约翰-卡马克(John Carmack)。事实上早在90年代初DOS时代,只要能在PC上搞个小动画都能让人惊叹一番的时候,John Carmack就推出了石破天惊的Castle Wolfstein, 然后再接再励,doom, doomII, Quake...每次都把3-D技术推到极致。他的3D引擎代码资极度高效,几乎是在压榨PC机的每条运算指令。当初MS的Direct3D也得听取他的意见,修改了不少API。    最近,QUAKE的开发商ID SOFTWARE 遵守GPL协议,公开了QUAKE-III的原代码,让世人有幸目睹Carmack传奇的3D引擎的原码。    这是QUAKE-III原代码的下载地址:    http://www.fileshack.com/file.x?fid=7547 (下面是官方的下载网址,搜索 “quake3-1.32b-source.zip” 可以找到一大堆中文网页的 ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip )    我们知道,越底层的函数,调用越频繁。3D引擎归根到底还是数学_运算。那么找到最底层的数学_运算函数(在game/code/q_math.c), 必然是精心编写的。里面有很多有趣的函数,很多都令人惊奇,估计我们几年时间都学不完。 在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 = 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; }     函数返回1/sqrt(x),这个函数在图像处理中比sqrt(x)更有用。     注意到这个函数只用了一次叠代!(其实就是根本没用叠代,直接运算)。编译,实验,这个函数不仅工作的很好,而且比标准的sqrt()函数快4倍!要知道,编译器自带的函数,可是经过严格仔细的汇编优化的啊!       这个简洁的函数,最核心,也是最让人费解的,就是标注了“what the fuck?”的一句       i = 0x5f3759df - ( i >> 1 ); 再加上y = y * ( threehalfs - ( x2 * y * y ) ); 两句话就完成了开方运算!而且注意到,核心那句是定点移位运算,速度极快!特别在很多没有乘法指令的RISC结构CPU上,这样做是极其高效的。 算法的原理其实不复杂,就是牛顿迭代法,用x-f(x)/f'(x)来不断的逼近f(x)=a的根。 简单来说比如求平方根,f(x)=x^2=a ,f'(x)= 2*x,f(x)/f'(x)=x/2,把f(x)代入 x-f(x)/f'(x)后有(x+a/x)/2,现在我们选a=5,选一个猜测值比如2, 那么我们可以这么算 5/2 = 2.5; (2.5+2)/2 = 2.25; 5/2.25 = xxx; (2.25+xxx)/2 = xxxx ... 这样反复迭代下去,结果必定收敛于sqrt(5),没错,一般的求平方根都是这么算的 但是卡马克(quake3作者)真正牛B的地方是他选择了一个神秘的常数0x5f3759df 来计算那个猜测值 就是我们加注释的那一行,那一行算出的值非常接近1/sqrt(n),这样我们只需要2次牛 顿迭代就可以达到我们所需要的精度. 好吧 如果这个还不算NB,接着看: 普渡大学的数学家Chris Lomont看了以后觉得有趣,决定要研究一下卡马克弄出来的 这个猜测值有什么奥秘。Lomont也是个牛人,在精心研究之后从理论上也推导出一个 最佳猜测值,和卡马克的数字非常接近, 0x5f37642f。卡马克真牛,他是外星人吗? 传奇并没有在这里结束。Lomont计算出结果以后非常满意,于是拿自己计算出的起始 值和卡马克的神秘数字做比赛,看看谁的数字能够更快更精确的求得平方根。结果是 卡马克赢了... 谁也不知道卡马克是怎么找到这个数字的。 最后Lomont怒了,采用暴力方法一个数字一个数字试过来,终于找到一个比卡马克数 字要好上那么一丁点的数字,虽然实际上这两个数字所产生的结果非常近似,这个暴 力得出的数字是0x5f375a86。 Lomont为此写下一篇论文,"Fast Inverse Square Root"。 论文下载地址: http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf http://www.matrix67.com/data/InvSqrt.pdf 点击此处下载 ourdev_714253IQ3KPV.pdf(文件大小:148K) (原文件名:InvSqrt.pdf)   参考:<IEEE Standard 754 for Binary Floating-Point Arithmetic><FAST INVERSE SQUARE ROOT> 最后,给出最精简的1/sqrt()函数: float InvSqrt(float x) {    float xhalf = 0.5f*x;    int i = *(int*)&x; // get bits for floating VALUE    i = 0x5f375a86- (i>>1); // gives initial guess y0    x = *(float*)&i; // convert bits BACK to float    x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy    return x; }   大家可以尝试在PC机、51、AVR、430、ARM、上面编译并实验,惊讶一下它的工作效率。 ==============增加================ 看matrix67大侠的解释 http://www.matrix67.com/blog/archives/362 这样的代码速度肯定飞快,我就不用多说了;但算法的原理是什么呢?其实说穿了也不是很神,程序首先猜测了一个接近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的是那个神秘的0x5f3759df,因为0x5f3759df - (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的,只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事,很少有人说得清楚。这篇论文(就是上面的附件)比较科学地解释了这个常数。


声明:转自ourdev.cn原帖地址: http://www.ourdev.cn/bbs/bbs_content_all.jsp?bbs_sn=4547125 ourdev.cn上的帖子转自 http://bbs.mydigit.cn/read.php?tid=168216    正文: 花了近20米,买了一个20字节的内存。注意,是"字节"! 其实这是70年代国产的磁芯存储器。我一直都想收藏一块这种存储器,这次终于有了机会。此内存为纯手工制造,其飞线技术实在令人惊叹!!! 磁芯存储器是华裔科学家王安的发明。在那个年代,这种发明可谓是突破性的,堪称计算机史上的里程碑。大家可以自己搜索一下王安的资料。 下面看图! 这是德国人做的同样产品:           美国人的,看看差距:    最后贴一段原理: The diagram illustrates an array of rings threaded on a grid of wires,   X1 to X4 and Y1 to Y4. If a sufficiently large current is passed along the wire X3,   then a magnetic field is generated around the wire and all the cores threaded on the wire in the X3 row will become magnetised.   They will remain magnetised when the current is switched off. Similarly, if a large current is passed along the wire Y3, all the Y3 cores will become magnetised. If a small current is passed along the wire X3, the field produced is not sufficient to have any effect on the cores. For a given arrangement, there is a particular current which is just sufficient to magnetise the cores. Now, here comes the clever bit. If a current equal to half this magnetising current is passed along X3 and another half current is passed along Y3, then only the red core at the intersection will receive the full magnetic field.   The red core will be magnetised but all the other cores will be unaffected. If the direction of the currents in X3 and Y3 is now reversed,   then the direction of magnetisation of the red core will be reversed, but again, no other cores will be affected. So far, we have been able to select a particular core and set it into one of two possible states, equivalent to "0" and "1".   It doesn't matter which direction of magnetisation we chose to represent a "1"   but we do need to be able to detect which of the two possible states a particular core is in. How can we do this? The diagram shows a third wire (the sense wire) threaded through all cores.   Now, when the core changes its magnetic state, the magnetic field inside the ring suddenly flips direction.   This moving magnetic field generates a small electrical current in the sense wire,   which can be amplified and detected. So, if we write a "1" to a particular core and this core is in the "0" state,   the the field will flip and a pulse will be detected in the sensing wire.   On the other hand, if the core was in the "1" state,   writing a "1" would have no effect and no pulse would appear on the sense winding.   In this way, the state of a particular core can be detected. Note that the act of reading core memory is destructive.   In normal use, the value read would have to be stored and then the core would have to be remagnetised in its original state. Although the action of reading is destructive, once written,   core memory will retain its contents indefinitely (or for a very long time). It does not require any power to maintain its contents.






nkc production Server  https://github.com/kccd/nkc

科创研究院 (c)2005-2016

蜀ICP备11004945号-2 川公网安备51010802000058号