計算量の少ないｎ乗根の求め方

質問

現在C++であるクラスのインスタンスaのN乗根を求める関数を作成中なのですが、どうしても実行時間が長くなってしまいます。
現在ニュートン法に則って
X(m+1)=((N-1)(Xm)^N+a)/(N*(Xm)^(N-1))
という漸化式を回して変化量が一定値以下になったら終了という関数なのですが、
値によっては累乗計算のところで時間を大幅にロスしてしまうようです。
原因としては累乗計算が同じ数をN回掛けるという単純な仕組みなため、
Nが大きすぎるとループがなかなか終わらないということがわかっています。
もしご存知であれば
1.極力累乗計算を使わないN乗根の求め方
2.計算量の少ない累乗計算の仕方
のどちらかを教えていただけないでしょうか？
なお、クラスを使っている関係上powなどの既存の関数は使えません。
よろしくお願いいたします。

回答No.2

Tacosan · ベストアンサー

ああ, そういうことですね.... じゃあ, (非負整数乗に限定して) べき乗を高速化する方法で:
普通は 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 回の乗算からなり, ほぼ最適です.

お礼

確認しました
お陰様でほぼ問題のないレベルの速さにすることができました
やはりオーダーがｎからlogｎになると格段に速さが違います
ありがとうございました

補足

なるほど、これは速そうですね。
ちょっと現在別のことで忙しいため確認できませんが、今週中くらいに試してみます。

回答No.1

Tacosan

「クラスを使っている関係上 pow などの既存の関数は使えません」は謎だなぁ.
その理由は?

補足

作成中のクラスは簡単にまとめると精度を任意に指定できるC#のDecimalのようなクラスです。
doubleに変換も一応はできるのでpowを使おうと思えばできるのですが、double以上の精度の場合丸め誤差が発生してしまうため使えないのです。