史丹利部落格: 9月 2012

2012年9月30日星期日

Jason Mraz / Mr.Curiosity 好奇先生

Jason Mraz / Mr.Curiosity 好奇先生

Hey Mr. Curiosity
嘿！好奇先生
Is it true what they've been saying about you
那些關於你的傳說，都是真的嗎？
Are you killing me?
你是存心整我嗎？
You took care of the cat already
收留了那隻小野貓
And for those who think it's heavy
是想向那些唱衰的人證明什麼
Is it the truth
這是真的嗎？
Or is it only gossip
又或者只是些流言蜚語？

Call it mystery or anything
就當作是個小祕密
Just as long as you'd call me
也打通電話跟我說吧！
I sent the message on did you get it when I left it
傳給你那則簡訊，有收到了嗎？
See this catastrophic event
眼看這場風雲變色的鬧劇
It wasn't meant to mean no harm
不可能沒有人受傷
But to think there's nothing wrong is a problem
裝作若無其事，才有夠荒唐
I'm looking for love this time
我想要的，不過就是愛啊！
Sounding hopeful but it's making me cry
看似滿懷希望的，卻落得流淚收場
Love is a mystery
愛怎麼讓人迷惘
Mr. Curious...
好奇先生啊...

Come back to me
請回到我身旁
Mr. waiting ever patient can't you see
永遠耐心守候的你，難道不明白？
That I'm the same the way you left me
我還是像你當初離開時那樣
In a hurry to spell check me
只要你一眼迅速打量
And I'm underlined already in envy green
我就被標上了嫉妒的綠
And pencil red
還畫上了一道紅筆
And I've forgotten what you've said
都忘了當時你說過了什麼
Will you stop working for the dead and return
但你何時才會死心塌地、回來這裡？
Mr. curious well I need some inspiration
好奇先生，請給我一點靈感
It's my birthday and I cannot find no cause for celebration
生日就要到了，可是有什麼值得慶祝的
The scenario is grave but I'll be braver when you save me
就算下一步是死棋，我也會變勇敢的，只要你肯伸出手
From this situation laden with hearsay
帶我走出這道聽塗說的境地

I'm looking for love this time
我想要的，不過就是愛啊！
Sounding hopeful but it's making me cry
看似滿懷希望的，卻落得流淚收場
And love is a mystery
愛怎麼讓人迷惘
Mr. Curiosity
好奇先生啊...
Be Mr. please
何不做個好好先生
Do come and find me, oh
飛奔回到我身邊
Find, find me, find me
回到我身邊、我身邊

I'm looking for love this time
我想要的，不過就是愛啊！
Sounding hopeful but it's making me cry
看似滿懷希望的，卻落得流淚收場
Trying not to ask why
我試著不去追究
Cause love is a mystery
愛怎麼讓人迷惘
Mr. curiosity
好奇先生啊...
Be Mr. please
何不做個好好先生
Do come and find me
回到我身邊

Love is blinding when the timing's never right
愛是盲目的，錯的時間遇不到對的人
Oh who am I to beg for difference
我又憑什麼以為自己與眾不同
Finding love in just an instant
能在一瞬間就認定了真愛？
Well I dont mind, at least I've tried
可是我不在乎，至少我努力過了
And I tried, I tried...
一再而再地，努力過了...

-----------------------------------------------------------------------------------
Jason Mraz( 傑森．瑪耶茲 )
出生自美國維吉尼亞的一個樸實小鎮的Jason Mraz，巨蟹座，在紐約唸大學的時候主修音樂劇，有一天他拿起吉他，突然發現自己的天命，於是便在畢業之後，跑到聖地牙哥當起街頭藝人。在那段時期，他和自稱是靈媒的流浪漢，成為心靈夥伴，他也開始四處流浪探索人生，並在這過程當中，很幸運地遇到生命中的貴人--知名音樂人鼓手Toca Rivera，兩人一同演出的精彩現場表演，也成為當時美國西岸網路間，最廣為流傳的行家級必備珍藏。Jason Mraz這位出色的素人歌手，在2002順利獲得唱片合約，推出首張專輯'Waiting For My Rocket To Come'，專輯一推出，隨即攻下全美熱門潛力榜亞軍，並獲得了白金銷售認證，當中的「The Remedy (I Won't Worry)」、「You and I Both」也都成為傳唱度極高的單曲。2005發行第二張原創大碟'Mr. A-Z'，甫發行即空降美國告示牌TOP5，而Jason擅長把玩文字的創意，也在這張專輯裡作了更淋漓盡致的發揮。
Jason Mraz二三事

2012年9月13日星期四

An intro to modern OpenGL

2012年9月1日星期六

John Carmack密码：0x5f3759df

John Carmack密码：0x5f3759df

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

我们知道，越底层的函数，调用越频繁。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

return y;

}

函数返回1/sqrt(x)，这个函数在图像处理中比sqrt(x)更有用。

注意到这个函数只用了一次叠代！（其实就是根本没用叠代，直接运算）。编译，实验，这个函数不仅工作的很好，而且比标准的sqrt()函数快4倍！要知道，编译器自带的函数，可是经过严格仔细的汇编优化的啊！

这个简洁的函数，最核心，也是最让人费解的，就是标注了“what the ***?”的一句

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”。

=======================================================

SquareRootFloat函数最关键的一句就是 i=0x5f3759df-(i>>1);

以下是对它的部分解释：

牛顿迭代法最关键的地方在于估计第一个近似根。如果该近似根与真根足够靠近的话,那么只需要少数几次迭代,就可以得到满意的解。

接着,我们要设法估计第一个近似根。这也是上面的函数最神奇的地方。它通过某种方法算出了一个与真根非常接近的近似根,因此它只需要使用一次迭代过程就获得了较满意的解。它是怎样做到的呢？所有的奥妙就在于这一行：

i = 0x5f3759df – (i >> 1); // 计算第一个近似根

超级莫名其妙的语句,不是吗？但仔细想一下的话,还是可以理解的：float类型的数据在32位系统上是这样表示的。

bits：31 30 … 0

31：符号位

30-23：共8位,保存指数（E）

22-0：共23位,保存尾数（M）

所以,32位的浮点数用十进制实数表示就是：M*2^E。开根然后倒数就是：M^(-1/2)*2^(-E/2)。现在就十分清晰了。语句 i>>1其工作就是将指数除以2,实现2^(E/2)的部分。而前面用一个常数减去它,目的就是得到M^(1/2)同时反转所有指数的符号。

============================================

参考：

最后，给出最精简的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 BACKto float

x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy

return x;

}

PS. 这个之所以重要，是因为求开根号倒数这个动作在 3D 运算 (向量运算的部份) 里面常常会用到，如果你用最原始的 sqrt() 然后再倒数的话，速度比上面的这个版本大概慢了四倍吧… XD

資料來源:

http://leonida0921.wordpress.com/2010/11/05/0x5f3759df/

訂閱：文章 (Atom)

史丹利部落格

2012年9月30日星期日

Jason Mraz / Mr.Curiosity 好奇先生

2012年9月13日星期四

An intro to modern OpenGL

2012年9月1日星期六

John Carmack密码：0x5f3759df

一個小故事讓我們明白資金流通的意義

搜尋此網誌

2012年9月30日 星期日

Jason Mraz / Mr.Curiosity 好奇先生

2012年9月13日 星期四

An intro to modern OpenGL

2012年9月1日 星期六

John Carmack密码：0x5f3759df

一個小故事讓我們明白資金流通的意義

2012年9月30日星期日

2012年9月13日星期四

2012年9月1日星期六