詳解基于john Carmark的密碼

2020-02-24 14:32:21

字體：大中小

來源：轉載

供稿：網友

? ? ? 密碼是一種用來混淆的技術，而John是一款免費開源軟件，基于對字典密碼的破解，很多人認為改變計算技術的是9個算法，這種算法是John Carmark研發的，你對john Carmark的密碼了解嗎？不了解的朋友們現在小編為你詳解基于john Carmark的密碼。

有人在Quake III的源代碼里面發現這么一段用來求平方根的代碼:

/*================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? = 0x5f3759df - ( i >> 1 );? //注意這一行
??? y? = * ( float * ) &i;
??? y? = y * ( f - ( x * y * y ) );
??? y? = y * ( f - ( x * y * y ) );
??? return number * y;
}

x5f3759df？這是個什么東西？學過數值分析就知道，算法里面求平方根一般采用
的是無限逼近的方法，比如牛頓迭代法，抱歉當年我數值分析學的太爛，也講不清楚
。簡單來說比如求5的平方根，選一個猜測值比如2，那么我們可以這么算

/2 = 2.5; 2.5+2/2 = 2.25; 5/2.25 = xxx; 2.25+xxx/2 = xxxx ...
這樣反復迭代下去，結果必定收斂于sqrt(5)，沒錯，一般的求平方根都是這么算的
。而卡馬克的不同之處在于，他選擇了一個神秘的猜測值0x5f3759df作為起始，使得
整個逼近過程收斂速度暴漲，對于Quake III所要求的精度10的負三次方，只需要一
次迭代就能夠得到結果。

好吧，如果這還不算牛b，接著看。

普渡大學的數學家Chris Lomont看了以后覺得有趣，決定要研究一下卡馬克弄出來的
這個猜測值有什么奧秘。Lomont也是個牛人，在精心研究之后從理論上也推導出一個
最佳猜測值，和卡馬克的數字非常接近, 0x5f37642f?？R克真牛，他是外星人嗎？

傳奇并沒有在這里結束。Lomont計算出結果以后非常滿意，于是拿自己計算出的起始
值和卡馬克的神秘數字做比賽，看看誰的數字能夠更快更精確的求得平方根。結果是
卡馬克贏了... 誰也不知道卡馬克是怎么找到這個數字的。

最后Lomont怒了，采用暴力方法一個數字一個數字試過來，終于找到一個比卡馬克數
字要好上那么一丁點的數字，雖然實際上這兩個數字所產生的結果非常近似，這個暴
力得出的數字是0x5f375a86。

Lomont為此寫下一篇論文，"Fast Inverse Square Root"。

我把這個函數用C#就行了一下改寫：

using System;
?using System.Collections.Generic;
?using System.Text;

?namespace ConsoleApplication1
?{
???? class Program
???? {
???????? static void Main(string[] args)
??????? {
??????????? Console.WriteLine("Carmark's method:");
??????????? Console.WriteLine(SquareRootFloat(3.0f).ToString());
??????????? Console.WriteLine("Use Math.Sqrt() method:");
??????????? Console.WriteLine(((float)Math.Sqrt(3.0)).ToString());
??????????? Console.Read();
??????? }

??????? private static float SquareRootFloat(float number)
??????? {

??????????? long i;
??????????? float x, y;
??????????? const float f = 1.5F;
??????????? x = number * 0.5F;
??????????? y? = number;
??????????? unsafe
??????????? {
??????????????? i? = * ( long * ) &y;
??????????????? i? = 0x5f3759df - ( i >> 1 );? //注意這一行
??????????????? y? = * ( float * ) &i;
??????????? }
??????????? y? = y * ( f - ( x * y * y ) );
??????????? y? = y * ( f - ( x * y * y ) );
??????????? return number * y;
??????? }
??? }
}