1

[質問をより「有用」で明確になるようにグローバルに編集しました]

expcmathでの関数の実装の複雑さについて疑問に思いました。

複雑さとは、可能であればアルゴリズムの複雑さを意味します。それ以外の場合、浮動小数点演算と比較したコスト（たとえば追加）

次の行：

double x = 3;
double y = std::exp(x);

コンパイル先：

...
19,23d16
       movq    %rax, -40(%rbp)
       movsd   -40(%rbp), %xmm0
       call    exp
       movsd   %xmm0, -40(%rbp)
       movq    -40(%rbp), %rax
...

exp実行時に動的にロードする必要がありますが、実装アルゴリズムの複雑さに関する多くの情報を見つけることができません。特別なプロセッサ命令への呼び出しはないようです（少なくともgccを使用するx86_64プラットフォームでは）ので、どこかに実装が見つからないはずです。私の考えでは、アルゴリズムは入力のバイナリ表現を使用して非常に複雑さが弱いと思われますが、このトピックに関する貴重なリファレンスを見つけることができませんでした。

この場合、アルゴリズムの複雑さについて話すことは実際には不可能であり、テストすることしかできません（以下の回答を参照）が、浮動小数点演算とexpの呼び出しの違いを客観的に定量化する方法がわかりません。

4

4 に答える 4

4

MSVC9コンパイラは特定のテーブル、ビットマスク、バイアスを含むビットマジックを実行するため、複雑さは実際には一定のようです。結局のところ、ブランチはほとんどないので、すべての命令パイプラインが大いに役立つはずです。以下は実際に行うことです。

unpcklpd    xmm0,xmm0 
movapd      xmm1,xmmword ptr [cv] 
movapd      xmm6,xmmword ptr [Shifter] 
movapd      xmm2,xmmword ptr [cv+10h] 
movapd      xmm3,xmmword ptr [cv+20h] 
pextrw      eax,xmm0,3 
and         eax,7FFFh 
mov         edx,408Fh 
sub         edx,eax 
sub         eax,3C90h 
or          edx,eax 
cmp         edx,80000000h 
jae         RETURN_ONE 
mulpd       xmm1,xmm0 
addpd       xmm1,xmm6 
movapd      xmm7,xmm1 
subpd       xmm1,xmm6 
mulpd       xmm2,xmm1 
movapd      xmm4,xmmword ptr [cv+30h] 
mulpd       xmm3,xmm1 
movapd      xmm5,xmmword ptr [cv+40h] 
subpd       xmm0,xmm2 
movd        eax,xmm7 
mov         ecx,eax 
and         ecx,3Fh 
shl         ecx,4 
sar         eax,6 
mov         edx,eax 
subpd       xmm0,xmm3 
movapd      xmm2,xmmword ptr Tbl_addr[ecx] 
mulpd       xmm4,xmm0 
movapd      xmm1,xmm0 
mulpd       xmm0,xmm0 
addpd       xmm5,xmm4 
mulsd       xmm0,xmm0 
addsd       xmm1,xmm2 
unpckhpd    xmm2,xmm2 
movdqa      xmm6,xmmword ptr [mmask] 
pand        xmm7,xmm6 
movdqa      xmm6,xmmword ptr [bias] 
paddq       xmm7,xmm6 
psllq       xmm7,2Eh 
mulpd       xmm0,xmm5 
addsd       xmm1,xmm0 
orpd        xmm2,xmm7 
unpckhpd    xmm0,xmm0 
addsd       xmm0,xmm1 
add         edx,37Eh 
cmp         edx,77Ch 
ja          ADJUST 
mulsd       xmm0,xmm2 
sub         esp,10h 
addsd       xmm0,xmm2 
movlpd      qword ptr [esp+4],xmm0 
fld         qword ptr [esp+4] 
add         esp,10h 
ret
于 2010-10-20T17:11:22.390 に答える
4

一般的に言えば、プリミティブ型の複雑さは非常に高速である必要があります。コメンテーターが言及しているように、そのための指示がある場合もあります。よく知られている高速アルゴリズムがない場合でも、Knuth にはそのようなことに関する優れたセクションがあります。

べき乗の通常の実装は、2 乗と乗算です。これは、任意のべき乗をいくつかの数の 2 乗と最大でもう 1 つの乗算に分割できるという観測を利用しています。の基本アルゴリズムはここn**kで与えられ、O ( lg k) です。

于 2010-10-20T16:27:47.660 に答える
2

ここでは、命令expを使用する高速な実装を見つけることができます。SSE

于 2010-10-20T16:53:55.803 に答える
1

他の浮動小数点演算にかかる時間と比較して、べき乗にかかる時間に関心がありますか？それは実装ごとに、またコンピューターごとに異なります（1つは異なる数学プロセッサーを使用している場合があります）ので、私たちが与えることができる答えは1つではありません。

知りたい場合の正しいアプローチは、テスト関数を作成して時間を計ることです。百万の浮動小数点割り当てをループして時間を計り、次に指数と時間の百万の浮動小数点割り当てをループしてそれを減算します。割り当ての結果を使用しないかのように、これのオプティマイザに注意してください。ループ全体を削除できます。ループのサイズによって変化しない非常に高速なランタイムによって、あなたはそれを知っているでしょう。

于 2010-10-20T17:11:00.097 に答える