I wanted to know what is the worst case time-complexity of the pow() function that's built in c++?
質問する
21771 次
3 に答える
17
それは、基礎となるアーキテクチャに依存します。最も一般的なデスクトップ アーキテクチャである x86 では、これは一定時間の操作です。
x86 での実装方法の詳細については、この質問を参照してください: How to: pow(real, real) in x86
于 2012-11-16T14:10:11.403 に答える
2
これが1つの実装です。見てください。確かに、これはかなり複雑なコードで、19 の特殊なケースがあります。時間計算量は、渡された値に依存していないようです。
以下は、 の計算に使用される方法の簡単な説明ですpow(x,y)。
Method: Let `x = 2 * (1+f)`
log2(x)次の 2 つの部分を 計算してlog2(x) = w1 + w2返しw1ます53-24 = 29。
y*log2(x) = n+y'多精度演算をシミュレートして実行します|y'|<=0.5。戻る
x**y = 2**n*exp(y'*log2)
于 2012-11-16T14:10:46.727 に答える
1
あなたが使用しているシステム/アーキテクチャについて言及していないため、推測のままです.
ただし、詳細を探しているのではなく、自由に利用できる実装のコードを閲覧したいだけの場合は、 http://www.netlib.org/fdlibm/、具体的にはhttp://www.netlib.org/fdlibm/w_powを参照してください。 .c
背景の詳細については、この質問の回答を参照してください: https://stackoverflow.com/a/2285277/25882
于 2012-11-16T14:21:59.517 に答える