![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
現在C++であるクラスのインスタンスaのN乗根を求める関数を作成中なのですが、どうしても実行時間が長くなってしまいます。
現在ニュートン法に則って
X(m+1)=((N-1)(Xm)^N+a)/(N*(Xm)^(N-1))
という漸化式を回して変化量が一定値以下になったら終了という関数なのですが、
値によっては累乗計算のところで時間を大幅にロスしてしまうようです。
原因としては累乗計算が同じ数をN回掛けるという単純な仕組みなため、
Nが大きすぎるとループがなかなか終わらないということがわかっています。
もしご存知であれば
1.極力累乗計算を使わないN乗根の求め方
2.計算量の少ない累乗計算の仕方
のどちらかを教えていただけないでしょうか?
なお、クラスを使っている関係上powなどの既存の関数は使えません。
よろしくお願いいたします。
No.2ベストアンサー
- 回答日時:
ああ, そういうことですね.... じゃあ, (非負整数乗に限定して) べき乗を高速化する方法で:
普通は 2乗と乗算を組合せる方法を使うと思います. 「ロシア乗算」などと言われる方法のべき乗版です.
例えば
double pow2(double x, unsigned int n)
{
double ans = 1;
while (n) {
if (n % 2) {
ans *= x;
}
x *= x;
n >>= 1;
}
return ans;
}
でしょうか. 全ての n に対して最適ということではない (n = 15 だと「3乗してから 5乗」の方が速い) のですが, たかだか log n 回の 2乗と同じくたかだか log n 回の乗算からなり, ほぼ最適です.
確認しました
お陰様でほぼ問題のないレベルの速さにすることができました
やはりオーダーがnからlognになると格段に速さが違います
ありがとうございました
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 a乗根の中にb乗根がありそのまた中にc乗根があるような計算をと呼ぶのでしょうか 4 2022/06/24 09:00
- C言語・C++・C# C言語 3 2022/10/04 15:07
- その他(ソフトウェア) F-BASICで計算中の実行が中途で勝手に止まり、大変困っています。 2 2023/03/02 16:15
- Excel(エクセル) エクセル・スプレッドシートで、一定数を超えたらゼロから再累計する方法 8 2022/05/28 03:52
- 数学 虚数単位:i、この4乗根を求める解答したものの疑問です。 1 2022/10/25 00:43
- 化学 化学のエンタルピ変化を求め方について ある例題では各物質のモール数を換算して計算することもあり、ある 1 2022/06/20 23:22
- Excel(エクセル) ExcelのCOUNTIF関数について COUNTIF関数を使って1の目の累積回数を計算したいのです 3 2023/06/13 22:41
- 数学 『最後の自然数はどんな数か』 3 2023/06/26 20:38
- Visual Basic(VBA) Excel のユーザー定義関数でソルバーが動作しない 1 2022/09/05 19:51
- 数学 8 x^3 - 6 x + 1 3 2022/11/22 16:55
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
変化させるセルが変化しない
-
EXCELなどで「返す」という表現
-
C言語で電卓を作成する。修正お...
-
引き放し法による除算アルゴリ...
-
lexとyaccでのプログラミング
-
バッチファイルでウインドウを...
-
アドオン利率を実質年率に変換
-
VBAプログラミング
-
再帰呼び出しの計算量
-
VBA 九九 Do While
-
サインカーブを計算したい
-
コマンドプロンプト内で右揃え...
-
計算量オーダーについて O(1/n...
-
パソコン
-
移動平均を計算するプログラム
-
MATLABの積分について
-
四則演算プログラム(入力式の...
-
【fortran77】データ行数のカウ...
-
pythonによる日の出日の入り計算
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
変化させるセルが変化しない
-
排他的論理和 BCC(水平パリテ...
-
VBAの再計算が反映されない件に...
-
VBAで関数をつくる
-
バッチファイルでウインドウを...
-
モジュラス103の計算とは何でし...
-
EXCELなどで「返す」という表現
-
数値計算の高速化 (cos, sin, exp)
-
傾いた四角形内の範囲の条件式
-
骨折リスク評価のFRAXについて...
-
matlab計算での進捗状況を知りたい
-
Excel VBAにてFFT
-
C言語についてです。 再帰を使...
-
C言語について 下の画像は do-w...
-
アドオン利率を実質年率に変換
-
エクセルで特定のセルのみを任...
-
電卓でmodの計算
-
引き放し法による除算アルゴリ...
-
y=(x^2 +3x+1)^4を微分の定義を...
おすすめ情報