5

C# の Math.Pow(double x, double y) や C++ の math.h pow-function などの累乗関数を使用すると、一定時間で実行されますか?

私が尋ねている理由は、フォーム (1-t)^n*p0 + ... + t^(n) * pN の「事前計算された」ベジェ関数が線形時間で実行できるかどうかを知りたいからです。制御点と t をパラメータとして取る De Casteljaus アルゴリズムの実装よりも高速です。

4

1 に答える 1

2

これらのメソッドは反復ベースの処理を使用して結果を取得し、2 つの反復の値の差が特定のエラー定数を下回ったときにのみ停止すると思います。

累乗演算の結果に非常に速く収束する反復法があります...したがって、それらはほぼ一定の時間であると思います。

この質問には、多くの優れた説明 があります。Math.Pow() は .NET Framework でどのように実装されていますか?

編集

http://math.stackexchange.comで作業するのに適した資料がたくさん見つかりました。

これは、人間の言語を使用して累乗を計算する方法を説明しているため、非常に興味深いものです。

考え

私は数学の天才ではありませんが、私が見る限り、所要時間は選択した値に大きく依存するのではなく、必要な正確な桁数に依存します。私が言おうとしているのは、それは引数に依存するということですが、最大値があります。

また、この理論を裏付けるために、次のアルゴリズム (Sun によって実装されている) を見てください: http://pastebin.com/LDjS5mAR。ループはなく、ifs のみです。それを実装した人たちが、彼らが望む固定精度を選択したためだと思います...そして、その精度を保証するために必要なすべての反復を拡張しました。

たとえば、反復回数が不変のループは、次のように簡単に展開できます。

for (int it = 0; it < 5; it++)
    a *= a;

以下と同じです:

a *= a; a *= a; a *= a; a *= a; a *= a;
于 2012-09-18T19:16:28.113 に答える