程序源代码中的注释经常是一个卧虎藏龙的地方，来看看这一辑国外某公司产品中的注释。注意：看的时候严禁喝水或进食。
亲爱的代码维护人员：
当您尝试优化这段代码但发现这是一个极端错误的决定的时候，请修改下面的计时器，以便警示后人。
总计浪费在这段代码的时间 = 16小时
真的很有问题
谨以此代码献给我的妻子达琳，感谢她一直支持我，还有我三个孩子和一只狗。
神奇代码，请勿改动
喝醉啦，迟些再弄
你可能会认为你读得懂以下的代码。但是你不会懂的，相信我吧。
要是你尝试玩弄这段代码的话，你将会在无尽的通宵中不断地咒骂自己为什么会认为自己聪明到可以优化这段代码。
好了，现在请关闭这个文件去玩点别的吧。
程序员1（于2002年6月7日）：在登陆界面临时加入一些调试代码
程序员2（于2007年5月22日）：临你个屁啊
反正这个办法就修复了问题，我也不知道为什么会这样
要理解什么是递归的话，请参考本文件的底部
（在文件的底部）
要理解什么是递归的话，请参考本文件的顶部
痛啊
亲爱的未来的我自己，请原谅我。
我有着难以表达的歉意。
我不对以下代码负责。
是他们逼我写的，是违背我意愿的。
疯了吗？欢迎来到斯巴达。
要是你能修正这个问题的话，我会送给你两个七十二岁的处女
没有注释留给你，难写的代码必定难读
IE 浏览器的 Hack （在这里先假设IE是浏览器）
有待修正。 修正什么啊？
要是再让我看到这种代码，我会带着枪来上班的
有只龙
在你阅读以下代码时，你要先搞懂为什么我在这样做。
我想读取一个根节点下面所有的子节点，以便控制根节点不会显示在选择框上。但那个傻逼的DBA找了一些某些傻逼的借口不让我用索引去读取这些数据，而要求我用他们傻逼的迭代器。所以有了以下代码。
当我写这段代码的时候.，只有老天和我自己知道我在做什么。
现在，只剩老天知道了。
====================中场休息坟割线====================
那么,为什么会有注释信誓旦旦的说不要在这段代码上浪费时间或者是不要试图去优化它呢?看看下面的就知道了-___,-我们平时经常会有一些数据运算的操作，需要调用sqrt，exp，abs等函数，那么时候你有没有想过：这个些函数系统是如何实现的？就拿最常用的sqrt函数来说吧，系统怎么来实现这个经常调用的函数呢？
虽然有可能你平时没有想过这个问题，不过正所谓是“临阵磨枪，不快也光”，你“眉头一皱，计上心来”，这个不是太简单了嘛，用二分的方法，在一个区间中，每次拿中间数的平方来试验，如果大了，就再试左区间的中间数；如果小了，就再拿右区间的中间数来试。比如求sqrt(16)的结果，你先试（0+16）/2=8，8*8=64，64比16大，然后就向左移，试（0+8）/2=4，4*4=16刚好，你得到了正确的结果sqrt(16)=4。然后你三下五除二就把程序写出来了：
float SqrtByBisection(float n) //用二分法
{
if(n<0) //小于0的按照你需要的处理
return n;
float mid,last;
float low,up;
low=0,up=n;
mid=(low+up)/2;
do
{
if(mid*mid>n)
up=mid;
else
low=mid;
last=mid;
mid=(up+low)/2;
}while(abs(mid-last) > eps);//精度控制
return mid;
}
然后看看和系统函数性能和精度的差别（其中时间单位不是秒也不是毫秒，而是CPU Tick，不管单位是什么，统一了就有可比性）
从图中可以看出，二分法和系统的方法结果上完全相同，但是性能上整整差了几百倍。为什么会有这么大的区别呢？难道系统有什么更好的办法？难道。。。。哦，对了，回忆下我们曾经的高数课，曾经老师教过我们“牛顿迭代法快速寻找平方根”，或者这种方法可以帮助我们，具体步骤如下：
相关的代码如下：
float SqrtByNewton(float x)
{
float val = x;//最终
float last;//保存上一个计算的值
do
{
last = val;
val =(val + x/val) / 2;
}while(abs(val-last) > eps);
return val;
}
然后我们再来看下性能测试：
哇塞，性能提高了很多，可是和系统函数相比，还是有这么大差距，这是为什么呀？想啊想啊，想了很久仍然百思不得其解。突然有一天，我在网上看到一个神奇的方法，于是就有了今天的这篇文章，废话不多说，看代码先：
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
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return 1/x;
}
然后我们最后一次来看下性能测试：
这次真的是质变了，结果竟然比系统的还要好。。。哥真的是震惊了！！！哥吐血了！！！一个函数引发了血案！！！血案，血案。。。
到现在你是不是还不明白那个“鬼函数”，到底为什么速度那么快吗？不急，先看看下面的故事吧：
引用
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的根。
没错，一般的求平方根都是这么循环迭代算的但是卡马克(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.pdfhttp://www.matrix67.com/data/InvSqrt.pdf参考：
最后，给出最精简的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、上面编译并实验，惊讶一下它的工作效率。
前两天有一则新闻，大意是说 Ryszard Sommefeldt 很久以前看到这么样的一段 code (可能出自 Quake III 的 source code)：
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}
他一看之下惊为天人，想要拜见这位前辈高人，但是一路追寻下去却一直找不到人；同时间也有其他人在找，虽然也没找到出处，但是 Chris Lomont 写了一篇论文 (in PDF) 解析这段 code 的算法 (用的是 Newton’s Method，牛顿法；比较重要的是后半段讲到怎么找出神奇的 0x5f3759df 的)。
PS. 这个 function 之所以重要，是因为求 开根号倒数 这个动作在 3D 运算 (向量运算的部份) 里面常常会用到，如果你用最原始的 sqrt() 然后再倒数的话，速度比上面的这个版本大概慢了四倍吧… XD
PS2. 在他们追寻的过程中，有人提到一份叫做 MIT HACKMEM 的文件，这是 1970 年代的 MIT 强者们做的一些笔记 (hack memo)，大部份是 algorithm，有些 code 是 PDP-10 asm 写的，另外有少数是 C code (有人整理了一份列表)
源代码下载地址:
http://blog.redfox66.com/post/story-about-sqrt.aspx=================我是无耻粉葛仙============外一篇:卖程序的小女孩
实验室里冷极了，没有窗户，不知道是白天还是黑夜。这是一周的最后一天——周末。在这又冷又黑的晚上，一个蓬头散发的小女孩在工位上坐着。她从家里出来的时候还穿着一件外套，但是有什么用呢？那是一件很大的外套──那么大，不知是哪一年买的。她工作的时候的，就把它脱掉了，实验室的师弟嘲笑说，可以拿它当抹布。
小女孩只好一个人做实验，一双小脚冻得红一块青一块的。她的破显示器屏幕上有一大段程序，手里草稿纸上还有一大段。这一整天，程序还是没调过，谁也没帮过她。
可怜的小女孩！她又冷又饿，哆哆嗦嗦地调程序。显示器的光落在她的干枯的长头发上，那头发卷曲着披在肩上，看上去很久没梳，不过她没注意这些。每个桌上都堆满了论文，实验室飘着一股油墨的香味，因为这是论文deadline的时间——她可忘不了这个。
她在一行代码上停了下来，蜷着趴在桌子上。她觉得更冷了。她不敢跟老板说，因为她程序没调过，没拿到一个数据，老板一定会骂她的。再说，换做别的题目跟这个一样难。她们头上只有paper，虽然网上可以下到一些现成的代码，还是仍然没法用。
她的头脑几乎绝望了。啊，哪怕一次小小的成功，对她也是有好处的！她敢把上万行的代码修改一遍。编译运行一下，来找找问题么？她终于按下回车键开始运行。哧！程序开始输出信息了！一行一行的log开始出来了！她把小手拢在显示器上。多么温暖多么明亮的字符啊，简直像一支小小的蜡烛。这是一道奇异的火光！小女孩觉得自己好像坐在一个19寸液晶大显示器前面，显示器还是全新锃亮的，颜色鲜艳，字迹清晰，上边显示着程序输出的正确结果，多么舒服啊！哎，这是怎么回事呢？她刚把头伸出去，想看的仔细一些，程序crash了，大显示器不见了。她坐在那儿，眼前的破显示器上一行刺眼的segmentfault。
她又编译了一遍运行。程序又开始输出信息了，给出log了。显示器的光落在桌子上，那儿忽然变得像打印出来的paper那样洁白工整，她可以一直看到 paper上的字迹。IEEE的logo，会议名称和日期，Abstract和Instroduction。更妙的是这篇paper的一作，赫然署着自己的名字！看上去那么诱惑，一直向这个穷苦的小女孩走来。这时候，程序又crash了，她面前只剩一张又硬又旧的桌子。
她又运行了一遍。这一回，她感觉自己坐在布置整齐的会议室里。条幅上写着“博士毕业答辩”，比她去年师姐毕业时用的条幅还要大，还要美。红色的条幅上贴着那几个白色的黑体字，投影仪屏幕上许多幅美丽的彩色画片，跟顶级会议里的presentation一个样，在向她眨眼睛。小女孩向画片伸出手去。这时候，程序又crash了。只见ppt上的图片越升越高，最后成了在天空中闪烁的星星。有一颗星星落下来了，在天空中划出了一道细长的红
光。
“有一个什么人快要死了。”小女孩说。唯一疼她的师姐毕业前的时候告诉过她：一颗星星落下来，就有一个灵魂要到图灵那儿去了。
她又编译了一遍。这一回，她把所有的数组size都设大了。师姐出现在亮光里，是那么温和，那么慈爱。
“师姐！”小女孩叫起来，“啊！请把我带走吧！我知道，程序一crash，您就会不见的，像那漂亮的显示器，发表的paper，布置好的答辩会议室一个样，就会不见的！”
她赶紧按了回车键，要把师姐留住。一大堆输出信息发出强烈的光，把实验室照得跟白天一样明亮。师姐从来没有像现在这样高大，这样美丽。师姐把小女孩抱起来，搂在怀里。
她们俩在光明和快乐中飞走了，越飞越高，飞到那没有代码，没有论文，也没有毕业的地方去了。
第二天清晨，这个小女孩坐在工位上，两腮通红，嘴上带着微笑。她死了，在周末的实验室累死了。新一周的太阳升起来了，照在她小小的尸体上。小女孩坐在那儿，手还按着在不知用过多少年的键盘上。
“她想自己把程序调一下……”人们说。谁也不知道她曾经看到过多么美丽的东西，她曾经多么幸福，跟着她师姐一起走向新世界的幸福中去。
