計算量の少ないｎ乗根の求め方
- C++でクラスのインスタンスaのN乗根を求める関数を作成しているが、実行時間が長くなる問題がある。
- ニュートン法を使用しているが、累乗計算の部分で時間をロスしている。
- 累乗計算を使用せずにN乗根を求める方法や、計算量の少ない累乗計算の方法を知りたい。
- ベストアンサー
計算量の少ないｎ乗根の求め方
現在C++であるクラスのインスタンスaのN乗根を求める関数を作成中なのですが、どうしても実行時間が長くなってしまいます。 現在ニュートン法に則って X(m+1)=((N-1)(Xm)^N+a)/(N*(Xm)^(N-1)) という漸化式を回して変化量が一定値以下になったら終了という関数なのですが、 値によっては累乗計算のところで時間を大幅にロスしてしまうようです。 原因としては累乗計算が同じ数をN回掛けるという単純な仕組みなため、 Nが大きすぎるとループがなかなか終わらないということがわかっています。 もしご存知であれば 1.極力累乗計算を使わないN乗根の求め方 2.計算量の少ない累乗計算の仕方 のどちらかを教えていただけないでしょうか？ なお、クラスを使っている関係上powなどの既存の関数は使えません。 よろしくお願いいたします。
- temp5963
- お礼率66% (4/6)
- C・C++・C#
- 回答数2
- ありがとう数4
- みんなの回答 （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 回の乗算からなり, ほぼ最適です.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
「クラスを使っている関係上 pow などの既存の関数は使えません」は謎だなぁ. その理由は?
補足
作成中のクラスは簡単にまとめると精度を任意に指定できるC#のDecimalのようなクラスです。 doubleに変換も一応はできるのでpowを使おうと思えばできるのですが、double以上の精度の場合丸め誤差が発生してしまうため使えないのです。
関連するQ&A
- 数値計算 ニュートン法に関する問題です
この問題のやり方を教えてください ｎの平方根をニュートン法で求める．ｎ＝１ √ｎ が f(x)＝(x^2)-n＝0 の解であることを利用し、ニュートン法を用いて √ｎ を求めるための漸化式を示せ． よろしくおねがいします
- ベストアンサー
- 数学・算数
- 4√16（四乗根16）を計算すると-2が入らないのはなぜ？
授業で先日指数の計算をやりました。 4乗根16というものを計算するとき(n√a)に当てはめて考えると 【nが偶数でaは正の数であるとき正の数aのｎ乗根はn√aと-n√aである。】と書いてありました。 そう考えると4√16は±2となるような気がするのですが答えはすべて2でした。。。 な、なぜ・・・・？ 初歩的な質問でホントごめんなさい。。。 回答おまちしています・・・。
- ベストアンサー
- 数学・算数
- ちょっと難解な漸化式の問題です！
ある関数の第n次導関数を求める際の計算過程で次の複雑な漸化式が出てきました。 a_(n+1)＝－(n+1)×a_n＋(－1)^n×n！ この漸化式は一体どのようにすれば解けるのでしょうか？ ただし、a_(n+1)、a_nはそれぞれ第n+1項、第n項を表しています。
- ベストアンサー
- 数学・算数
- 原始ｎ乗根
FMTの話しの中に、ｎを偶数として、 整数ω＞＝２とすると、P=1+ω^(n/2)上でωは原始ｎ乗根となる。 と書いてある。 たしかに、ωはｎ乗して初めて１とPを法として合同になる。 これは、Pが素数でなくても成立します。 しかし、 原始ｎ乗根の性質として ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) が成立すると書いてある。 ω＝２、ｎ＝6とすると、 ｊ＝１のときは 1+２+４+８+16+32＝63＝9*7≡0 mod(9) 9=2^(6/2)+1 j=2のときは、 １+４+16+64+256+1024＝1365＝151*9+6 アルゴリズムの設計と解析II （エイホ 他）の28ページには 原始ｎ乗根の定義の中の条件として、原始ｎ乗根は条件 ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) を満たさなくてはならない。 と書いてある。 さて、原始ｎ乗根の定義は何でしょうか？ 最初の２は原始ｎ乗根なのでしょうか？ Pには他に条件が付くのでしょうか？ ｊ に条件をつけるのでしょうか？ 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 高校数学 累乗根のうちの奇数乗根について
教えて下さい。 累乗根の計算でa>0,b>0のとき、 （ab）^(1/n)=a^(1/n)×b^(1/n) とありますが、ｎが奇数のときはa>0,b>0の条件は不要でしょうか。 例えは、a>0,b<0のとき、 （ab）^(1/n)=a^(1/n)×b^(1/n) としても正しいのでしょうか。 宜しくお願いします。
- ベストアンサー
- 数学・算数
お礼
確認しました お陰様でほぼ問題のないレベルの速さにすることができました やはりオーダーがｎからlogｎになると格段に速さが違います ありがとうございました
補足
なるほど、これは速そうですね。 ちょっと現在別のことで忙しいため確認できませんが、今週中くらいに試してみます。