0x5f3759df : Quake’s Fast Inverse Square Root (推倒技術高牆靠的是?)

相信有不少人早就看過這個演算法, 它來自雷神之鎚(Quake-III Arena)3D引擎的source code, 雖然它只是單純計算一個浮點數的“倒數平方根”, 但這運算卻是所有幾何運算的核心.
(如果沒看過的可以參考此中文網站:http://www.cnblogs.com/pkuoliver/archive/2010/10/06/sotry-about-sqrt.html)

不過哥想分享的不是這個演算法的原理, 而是一種它背後的動機 !

float invsqrt(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
	return y;
}

身為programmer看到這樣的code一定會佩服的五體投地. 一般求平方根就已經讓人頭痛了, 再加個倒數… 但是上面這個做法卻只需要 addition, multiplication 和 bit-shift. 是的你沒看錯, 縱使你學過數值分析/方法(Numeric Method) 你也會需要一個迴圈去迭代(iteration)出近似解, 你注意到了嗎? 這方法連迴圈都沒有 !? (相信你心裡也跟我一樣噴出 “WTF?”). 如果你沒學過牛頓法(Newton’s Method)可以去google一下, 他的價值在用有效的猜測去逼近你要求解的函數. 而上面的方法也是採用同樣的概念, 但做得更加極端 !

i = 0x5f3759df - ( i >> 1 );

這一行就是產生猜測值的過程, 而且是逼近到足夠精確, 以至於根本不需要迴圈再迭代下去 ! 注意到了嗎 ? “0x5f3759df” 這個 magic number 就是我想和大家分享的… 在電腦的世界裡, 數值並沒有“無限”的概念, 而是有限離散的, 可精確描述的存在, 因此造就了用 magic number 就可解決許多困難的問題. 這讓我想到駭客任務(The Matrix)第一集, Neo 重生後看透了數位訊號的世界, 能夠做出許多不可能的事情.

我聽過一句話說得很好, “解決問題前, 要先掌握問題的本質”, 世界上許多困難/無解的問題只是還未被看透本質. 在電腦的世界裡, 沒有門是打不開的, 沒有高牆是推不倒的, “Nothing is impossible!”

如果你想看懂它的原理, 就 google 它吧, 它太有名了 !
如果對這演算法的歷史有興趣的可以看看: http://shelfflag.com/rsqrt.pdf

Mac: Write NTFS 的方法

當你想要備份資料但身邊卻只有NTFS格式的隨身硬碟

那 paragon NTFS 這套軟體就是一個解決方案

paragon NTFS 是一套付費軟體

1. ntfsmac_trial.dmg 試用安裝檔

2. core_keygen.dmg 序號產生器

步驟一:

安裝 ntfsmac_trial

到序號時請選擇

步驟二:

安裝完成後請到Launchpad找到註冊ntfsmac後點開

會需要輸入Product Key 以及 Serial Number

此時點開core_keygen.dmg選擇版本號後點擊下方的”Generate”按鈕來產生序號

之後copy Product Key 以及 Serial Number 貼上就可以註冊完成了