c++ - c++ の実用的な計算の複雑さSQRT()

Question

間のCPUサイクル（または、本質的に「速度」）の違いは何ですか

 x /= y;

と

 #include <cmath>
 x = sqrt(y);

編集：操作が同等ではないことはわかっていx /= yます。ベンチマークとして恣意的に提案しているだけですx = sqrt(y)

Answer 1

あなたの質問に対する答えは、ターゲット プラットフォームによって異なります。最も一般的な x86 CPU を使用していると仮定して、このリンクを提供できますhttp://instlatx64.atw.hu/ これは、測定された命令レイテンシ (CPU が引数を取ってから結果を取得するのにかかる時間) のコレクションです。多くの x86 および x86_64 プロセッサでパイプライン化される方法。ターゲットが x86 でない場合は、自分でコストを測定するか、CPU のドキュメントを参照してください。

まず、操作の逆アセンブラーを取得する必要があります (gcc などのコンパイラーから、gcc file.c -O3 -S -o file.asmまたはデバッガーの助けを借りて、コンパイルされたバイナリーの逆アセンブルを介して)。操作では、値のロードと保存があり、追加でカウントする必要があることに注意してください。

friweb.hu からの 2 つの例を次に示します。

SQRT の Core 2 Duo E6700 レイテンシ (L) (x87、SSE、および SSE2 バージョンの両方)

• 32 ビット浮動小数点の場合は 29 ティック。64 ビット double の場合は 58 ティック。80 ビットの長さの double の場合は 69 ティック。

DIVIDE の (浮動小数点数の):

• 32 ビットの場合は 18 ティック。64 ビットの場合は 32 ティック。80 ビットの場合は 38 ティック

新しいプロセッサの場合、コストは低くなり、DIV と SQRT でほぼ同じです。たとえば、Sandy Bridge Intel CPU の場合です。

浮動小数点 SQRT は

• 32 ビットの場合は 14 ティック。64 ビットの場合は 21 ティック。80 ビットの場合は 24 ティック

浮動小数点 DIVIDE は

• 32 ビットの場合は 14 ティック。64 ビットの場合は 22 ティック。80 ビットの場合は 24 ティック

SQRT は、32 ビットの場合でも 1 ティック速くなります。

つまり: 古い CPU の場合、sqrt 自体は fdiv よりも 30 ～ 50 % 遅くなります。新しい CPU の場合、コストは同じです。新しい CPU の場合、両方の操作のコストが古い CPU の場合よりも低くなります。より長いフローティング形式の場合は、より多くの時間が必要です。たとえば、64 ビットの場合、32 ビットの場合よりも 2 倍の時間が必要です。しかし、80 ビットは 64 ビットに比べて安価です。

また、新しい CPU には、スカラー (x87) と同じ速度のベクトル演算 (SSE、SSE2、AVX) があります。ベクトルは 2 ～ 4 個の同じ型のデータです。同じ操作で複数の FP 値で動作するようにループを調整できる場合、CPU からより多くのパフォーマンスが得られます。

Answer 2

If the square root function isn't implemented in special hardware or software, most library functions would calculate it using Newton's method, which converges quadratically.

Newton's method is an iterative method: you make an initial guess, calculate a trial result, and use that for the next guess. You repeat until you think you have a result that's "close enough." It so happens that you can prove how many iterations you need with square root. Every time through the cycle you get another two digits of accuracy, so most implementations will converge to the precision limit of doubles in 8-9 cycles.

If you read this carefully, you'll see that the iterative Newton's method is doing two subtractions, one multiplication, and one division per iteration.

Answer 3

一般的な経験則として: 浮動小数点除算と平方根はどちらも (加算や乗算のような高速演算と比較して) 低速演算と見なされます。平方根は、除算とほぼ同じか、多少遅くなります (つまり、約 1 倍から 2 倍のパフォーマンスが低下します)。例: Pentium Pro

除算と平方根のレイテンシは、それぞれ 18 ～ 36 サイクルと 29 ～ 69 サイクルです。

より正確な答えを得るには、プラットフォームのアーキテクチャ マニュアルを掘り下げるか、ベンチマークを実行する必要があります。

注: 最近の多くのプラットフォームでは、sqrt とほぼ同じ速度の逆平方根も提供されていますが、より便利なことがよくあります (たとえば、invsqrt を使用すると、それぞれ 1 つの乗算で sqrt と div の両方を計算できます)。