9

pow() の高速な実装、たとえばこれは、高速な sqrt(x) よりも整数の平方根を取得する高速な方法であるかどうか疑問に思っています。私達はことを知っています

sqrt(x) = pow(x, 0.5f)

sqrt の高速な実装が見つからなかったため、自分で速度をテストすることはできません。私の質問は: pow(x, 0.5f) の高速実装は高速 sqrt(x) より高速ですか?

編集: 私は powf を意味しました - double の代わりに float を取る pow 。(ダブルは誤解を招きやすい)

4

3 に答える 3

23

C 標準ライブラリsqrtとに関してpowは、答えはノーです。

まず、pow(x, .5f)が の実装よりも高速である場合sqrt(x)、sqrt の維持を担当するエンジニアは実装を に置き換えpow(x, .5f)ます。

第 2 に、商用ライブラリでの sqrt の実装は、通常、そのタスクを実行するために特別に最適化されています。多くの場合、高性能ソフトウェアの作成に精通しており、プロセッサから最高のパフォーマンスを引き出すためにアセンブリ言語またはアセンブリ言語に近い言語で記述している人々によって最適化されています。

第 3 に、多くのプロセッサには、sqrt を実行したり、その計算を支援したりする命令があります。(通常、平方根の逆数の推定値を提供する指示と、その推定値を改善する指示があります。)

でも

リンクしたコード/あなたが尋ねた質問は、大まかに近似された をsqrt使用して大まかな近似を試みることに関するものですpow。

質問で言及されている pow 近似ルーチンの最終バージョンを C に変換し、 を計算したときの実行時間を測定しましたpow(3, .5)。また、システム (Mac OS X 10.8) の pow と sqrt、およびここでの sqrt 近似の実行時間も測定しました(1 回の反復と、最後に引数を掛けて、逆数ではなく平方根を取得します)。

まず、計算結果: pow 近似は 1.72101 を返します。sqrt 近似は 1.73054 を返します。システム pow および sqrt によって返される正しい値は 1.73205 です。

MacPro4,1 で 64 ビット モードで実行すると、pow 近似に約 6 サイクル、システム pow に 29 サイクル、平方根近似に 10 サイクル、システム sqrt に 29 サイクルかかります。これらの時間には、引数を読み込んで結果を保存するためのオーバーヘッドが含まれる場合があります (私は揮発性変数を使用して、コンパイラーが最適化しないように強制し、それ以外の場合は無駄なループ反復を測定できるようにしました)。

(これらの時間は「実効スループット」であり、実際には、ある呼び出しが開始されてから別の呼び出しが開始されるまでの CPU サイクル数です。)

于 2012-08-04T17:52:25.637 に答える
2

MSVC++ 2013 64 ビット モード、完全最適化で次のコードを実行した結果。sqrt() の最大 9 倍のパフォーマンス。

距離は 2619435809228.278300 です

Pow() の経過時間は 18413.000000 ミリ秒でした

距離は 2619435809228.278300 です

Sqrt() の経過時間は 2002.000000 ミリ秒でした

#define LOOP_KNT 249000000  // (SHRT_MAX * 1024)

int main(void)    {
    time_t start = clock();

    double distance = 0, result = 0;
    start = clock();
    for(int i=0; i<LOOP_KNT; i++) {
        result = pow(i, 0.50);
        distance += result;
    }
    printf("\nDistance is %f", distance);
   printf("\nPow() elapsed time was %f milliseconds", (double)clock() - (double)(start));

   distance = 0, result = 0;
   start = clock();
    for(int i=0; i<LOOP_KNT; i++) {
        result = sqrt(i);
        distance += result;
    }
    printf("\nDistance is %f", distance);
    printf("\nSqrt() elapsed time was %f milliseconds", (double)clock() - (double)(start));

   printf("\nHit any key to end program.\n");
   getchar();

   return 0;
}

手作業、理論化、または説教は必要ありません。ベンチマークを書いて結果を観察するだけです。

于 2014-02-07T20:50:58.323 に答える
1

一般に、エラーに対する同じ制約が与えられた場合、より具体的な問題は、より一般的な問題よりも最適化される可能性があります。

したがって、そのアルゴリズムを使用して、b を定数 0.5 に置き換えると、少なくともその pow() と同じくらい高速な sqrt() が得られます。定数になったので、コンパイラ (または人間) はそれに基づいて最適化を行うことができます。

pow() 関数は概算であり、(比較的) 大きな誤差があるため、ほとんどのライブラリ sqrt 関数ほど正確ではないことに注意してください。sqrt の実装を同じ近似限界まで緩和すると、実際には少なくとも同じくらい速くすることができます。

于 2012-08-04T17:51:47.217 に答える