維尼的蜂巢

RealTime??!! It’s amazing!!!!

InvSqrt 十二月 4, 2006

Filed under: 3D Graph — kevinlin @ 11:48 下午

今天看到這個http://blog.ijliao.info/archives/2006/12/04/2739/

裡面貼了在Beyond3D裡的一則新聞,主要是下面這段做<開根號的倒數1/sqrt>的code,他的寫法跟效能讓人感到非常神奇,最神奇的尤其是0x5f3759df這個數字,推導出的人肯定是個天才.

float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating value
i = 0x5f3759df – (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;
}
至於只想求Sqrt(float x),它是return 傳入值 * x

求root大家都用牛頓法來逼近一個近似值,這就不用說了,上面的code應該快在他用特別的方法做一些bit hack,還有那個magic number來得到一個initial guess,雖然我的也比一般使用1/sqrt快,但是相較之下顯的弱了一些,而且我作弊,是用SSE指令集,先用rsqrtss(這就已經是平方根倒數了)當做一個initial guess,然後再用牛頓法求root ,在不支援SSE指令集的機器上就沒用了,不過如果把上面那段改成SSE來做不知道效能會不會再提升一次😛 不過大概是沒辦法改,能改的話原作者就改了,有空來看看

下面這是我的實作方法,也不賴啊
float InvSqrt( float F )
{
 const float fThree = 3.0f;
 const float fOneHalf = 0.5f;
 float temp;

 __asm
 {
  movss xmm1,[F]
  rsqrtss xmm0,xmm1   // 1/sqrt estimate (12 bits)
       // 牛頓法的iteration  (X1 = 0.5*X0*(3-(Y*X0)*X0))
      //  我們只做一次iteration
  movss xmm3,[fThree]
  movss xmm2,xmm0
  mulss xmm0,xmm1   // Y*X0
  mulss xmm0,xmm2   // Y*X0*X0
  mulss xmm2,[fOneHalf]  // 0.5*X0
  subss xmm3,xmm0   // 3-Y*X0*X0
  mulss xmm3,xmm2   // 0.5*X0*(3-Y*X0*X0)
  movss [temp],xmm3
 }

 return temp;
}

所以結論在他的initial guess是:
int i = *(int*)&x; // get bits for floating value
i = 0x5f3759df – (i>>1); // gives initial guess y0
那個 i

而我的initial guess是:
rsqrtss xmm0,xmm1
那個xmm0
為什麼已經算出開根號倒數還要再算呢?? 因為我要讓他更快
規格書上rsqrtss是這樣運作的
DEST[31-0] ← APPROXIMATE(1.0/SQRT(SRC[31-0]));
假設一個暫存器有128bit,也就是說它只把後面的32bit拿來算然後丟出去,所以算出的只是一個近似值
我們就是需要這個近似值,然後再去用牛頓法逼近

 

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s