程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 基於John Carmark密碼詳解

基於John Carmark密碼詳解

編輯:C語言基礎知識

有人在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。卡馬克真牛,他是外星人嗎?

傳奇並沒有在這裡結束。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;
        }
    }
}


 第32、33行用了兩次牛頓迭代法,以達到一定的精度,當然你也可以自己控制精度,求出來的是y的平方根的倒數,所以最後返回為number*y.

SquareRootFloat函數最關鍵的一句就是 i=0x5f3759df-(i>>1);
以下是對它的部分解釋:

牛頓迭代法最關鍵的地方在於估計第一個近似根。如果該近似根與真根足夠靠近的話,那麼只需要少數幾次迭代,就可以得到滿意的解。

接著,我們要設法估計第一個近似根。這也是上面的函數最神奇的地方。它通過某種方法算出了一個與真根非常接近的近似根,因此它只需要使用一次迭代過程就獲得了較滿意的解。它是怎樣做到的呢?所有的奧妙就在於這一行:

i = 0x5f3759df - (i >> 1); // 計算第一個近似根

超級莫名其妙的語句,不是嗎?但仔細想一下的話,還是可以理解的:float類型的數據在32位系統上是這樣表示的。

bits:31 30 ... 031:符號位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. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved