最良の平方根を求める方法(精度VS速度)

作者:Mahmoud Hesham El-Magdoub
記事ソースリンク:http://www.codeproject.com/KB/cpp/Sqrt_Prec_VS_Speed.aspx
Technoratiラベル:平方根、アルゴリズム、速度、精度、Quake 3、c++、c
私はDirectXでゲームのプログラミングをするのが好きです.私のゲームで呼び出された関数の多くがMathにあることに気づいた.hにおける標準sprt法.だから、標準sqrt関数よりも速い関数を探さなければなりません.しばらくの間の探索を経て,sqrt関数よりも多くの関数が速いことが分かったが,これらの関数は常に精度と速度の間で折衷される解決法である.この文章の目的はプログラマーが彼らのプログラムに適した最良の平方根を求める方法を選択することを助けることである.
背景知識:この文章では、標準sqrt関数を参考に、12の異なる平方根を求める方法を比較します.各方法について,その精度と速度をsqrt関数と比較した.
1、各方法の動作原理を説明する2、平方根を計算する新しい方法を含まない.
アプリケーションコード:コードは簡単で、基本的には:1、main.cppはすべての方法を呼び出し,sqrt関数と比較した精度と速度をそれぞれ計算する.
2、SquareRootmethods.hこのヘッダファイルには、関数の実装と、これらの方法の参照が含まれています.
----------------------------------------------------
まず,参照としての標準sqrt関数の精度と速度を計算した.速度を計算するために,sqrt関数(M−1)を呼び出すのにかかる時間を記録した.この値をRefSpeedに私の参照値として割り当てます.
精度を計算するために、私は関数を呼び出すたびに、毎回の計算結果を加算し、変数RefTotalPrecisionに記録します.RefTotalPrecision変数は私の参考値です.
関数の実行時間の持続速度を記録するために、CDurationクラス(このリンクで見つけた)を適用しました.CDurationクラスのオブジェクトはdurです.

	for(int j=0;j<AVG;j++)	
	{	
	  dur.Start();
		
		for(int i=1;i<M;i++)
		   RefTotalPrecision+=sqrt((float) i);
	
      	 dur.Stop();
	
	  Temp+=dur.GetDuration();
	
	}
	
	RefTotalPrecision/=AVG;
	Temp/=AVG;

	
	RefSpeed=(float)(Temp)/CLOCKS_PER_SEC;

他のアルゴリズムについては同じ計算をしたが,最後にsqrtと比較した.

	for(int j=0;j<AVG;j++)	
	{	
	  dur.Start();
		
		for(int i=1;i<M;i++)
		    TotalPrecision+=sqrt1((float) i);
	
          dur.Stop();
	
	  Temp+=dur.GetDuration();
	
	}
	
	TotalPrecision/=AVG;
	Temp/=AVG;
		
	Speed=(float)(Temp)/CLOCKS_PER_SEC;

cout<<"Precision = "
<<(double)(1-abs((TotalPrecision-RefTotalPrecision)/(RefTotalPrecision)))*100<<endl;    

         

注意:1計算精度で誰が大きいか誰が小さいかを区別するのは意味がないと思いますのでabsで絶対値を取ります.2(次の2つのグラフについて)「精度テーブル」の数字は、計算精度(math.sqrtの精度に対して)が低下した割合を表し、「速度テーブル」の数値は(math.sqrtの速度に対して)の割合である.
(この段落はあまり理解していませんが、以下は原文です.
1、I Assume that the error in Precision whether larger or smaller than the reference is equal that's why i use "abs".  2、The Speed is refrenced as the actual percentage, while the Precision is referenced a decrease percentage. )
あなたは自分の好きなようにM値を修正することができて、私はM値を10000に初期化します.AVG値を変更することもできます.この値が高いほど、精度が高くなります.

#define M 10000   
#define AVG 10 

興味深いポイント:標準sqrt法の精度は最良ですが、他の関数は5倍以上速くできます.個人的に方法N#2を選びます.精度が高く、速度も速いからです.しかし、私はあなたに選択権を教えてあげましょう.
私は5つのサンプルを抽出して平均した.出力の結果図を次に示します.
 

注意:これらの関数の実行は、コンピュータの中央プロセッサに依存することが多いので、1台のコンピュータの結果は別のコンピュータとは異なります.
方法:Sqrt 1:参照リンク:http://ilab.usc.edu/wiki/index.php/Fast_Square_Rootアルゴリズム:Babylonian Method+IEEE 32 bit浮動小数点数表現の制御.

float sqrt1(const float x)  
{
  union
  {
    int i;
    float x;
  } u;
  u.x = x;
  u.i = (1<<29) + (u.i >> 1) - (1<<22); 
  
  // Two Babylonian Steps (simplified from:)
  // u.x = 0.5f * (u.x + x/u.x);
  // u.x = 0.5f * (u.x + x/u.x);
  u.x =       u.x + x/u.x;
  u.x = 0.25f*u.x + x/u.x;

  return u.x;
}  
Sqrt2

Sqrt 2:参照リンク:http://ilab.usc.edu/wiki/index.php/Fast_Square_Rootアルゴリズム:The Magic Number(Quake 3)

#define SQRT_MAGIC_F 0x5f3759df 
 float  sqrt2(const float x)
{
  const float xhalf = 0.5f*x;
 
  union // get bits for floating value
  {
    float x;
    int i;
  } u;
  u.x = x;
  u.i = SQRT_MAGIC_F - (u.i >> 1);  // gives initial guess y0
  return x*u.x*(1.5f - xhalf*u.x*u.x);// Newton step, repeating increases accuracy 
}   

Sqrt 3:参照リンク:http://www.dreamincode.net/code/snippet244.htmアルゴリズム:Logbase 2 approximation and Newton's Method

float sqrt3(const float x)  
{
  union
  {
    int i;
    float x;
  } u;

  u.x = x;
  u.i = (1<<29) + (u.i >> 1) - (1<<22); 
  return u.x;
} 

Sqrt 4:リファレンスリンク:ずいぶん前にフォーラムで見たのですが、今は忘れてしまいました.リファレンスリンクがあれば連絡してください.アルゴリズム:Bakhsali Approximation

float sqrt4(const float m)
{
   int i=0; 
   while( (i*i) <= m )
          i++;
    i--; 
   float d = m - i*i; 
 float p=d/(2*i); 
 float a=i+p; 
   return a-(p*p)/(2*a);
}  

Sqrt 5:参照リンク:http://www.dreamincode.net/code/snippet244.htmアルゴリズム:Babylonian Method

   float sqrt5(const float m)
{
   float i=0;
   float x1,x2;
   while( (i*i) <= m )
          i+=0.1f;
   x1=i;
   for(int j=0;j<10;j++)
   {
       x2=m;
      x2/=x1;
      x2+=x1;
      x2/=2;
      x1=x2;
   }
   return x2;
}   

Sqrt 6:参照リンク:http://www.azillionmonkeys.com/qed/sqroot.html#calcmethアルゴリズム:IEEEに依存し、32 bitでのみ動作します.
(原文:Dependent on IEEE representation and only works for 32 bits)

double sqrt6 (double y) 
{
    double x, z, tempf;
    unsigned long *tfptr = ((unsigned long *)&tempf) + 1;
    tempf = y;
   *tfptr = (0xbfcdd90a - *tfptr)>>1; 
 x =  tempf;
 z =  y*0.5;                       
 x = (1.5*x) - (x*x)*(x*z);    //The more you make replicates of this statment the higher the 					//accuracy, here only 2 replicates are used  
  x = (1.5*x) - (x*x)*(x*z);       
  return x*y; 
  }  

Sqrt 7:参照リンク:http://bits.stephan-brumme.com/squareRoot.htmlアルゴリズム:IEEEに依存し、32 bitでのみ動作します.

float sqrt7(float x)
 {
   unsigned int i = *(unsigned int*) &x; 
   // adjust bias
   i  += 127 << 23;
   // approximation of square root
   i >>= 1; 
   return *(float*) &i;
 }   

Sqrt 8:参照リンク:http://forums.techarena.in/software-development/1290144.htmアルゴリズム:Babylonian Method

double sqrt9( const double fg)
{ 
 double n = fg / 2.0;
 double lstX = 0.0; 
 while(n != lstX)  
 { 
 lstX = n;
 n = (n + fg/n) / 2.0; 
 }
 return n;
 }  

Sqrt 9:参照リンク:http://www.functionx.com/cpp/examples/squareroot.htmアルゴリズム:Babylonian Method

 double Abs(double Nbr)
{ 
 if( Nbr >= 0 ) 
  return Nbr; 
 else
  return -Nbr;
}

double sqrt10(double Nbr)
{
 double Number = Nbr / 2; 
 const double Tolerance = 1.0e-7; 
 do
 {
  Number = (Number + Nbr / Number) / 2;
 }while( Abs(Number * Number - Nbr) > Tolerance);
	
 return Number;
}   

Sqrt10:
参照リンク:http://www.cs.uni.edu/~jacobson/C++/newton.html
アルゴリズム:Newton's Approximation Method

double sqrt11(const double number)e
{
const double ACCURACY=0.001;
double lower, upper, guess;

 if (number < 1)
 {
  lower = number;
  upper = 1;
 }
 else
 {
  lower = 1;
  upper = number;
 }

 while ((upper-lower) > ACCURACY)
 {
  guess = (lower + upper)/2;
  if(guess*guess > number)
   upper =guess;
  else
   lower = guess; 
 }
 return (lower + upper)/2;

}  

Sqrt 11:参照リンク:http://www.drdobbs.com/184409869;jsessionid=AIDFL 0 EBECDYLQE 1 GHOSKH 4 ATMY 32 JVN演算法則:Newton's Approximation Method

 double sqrt12( unsigned long N )
{
    double n, p, low, high;
    if( 2 > N )
        return( N );
    low  = 0;
    high = N;
    while( high > low + 1 )
    {
        n = (high + low) / 2;
        p = n * n;
        if( N < p )
            high = n;
        else if( N > p )
            low = n;
        else
            break;
    }
    return( N == p ? n : low );
}  

Sqrt 12:参照リンク:http://cjjscript.q8ieng.com/?p=32アルゴリズム:Babylonian Method

	double sqrt13( int n )
	{
		// double a = (eventually the main method will plug values into a)
		double a = (double) n;
		double x = 1;
 
		// For loop to get the square root value of the entered number.
		for( int i = 0; i < n; i++)
		{
			x = 0.5 * ( x+a / x );
		}
 
		return x;
	}  

最後に、この貧しい文章が興味のある人に少し役に立つことを望んでいます.
ping:自分の学習と翻訳を促進するために、レベルが限られています.間違いを指摘してください.