累乗計算のアルゴリズム

昨日ひらめいたー。
javaでついに作れたー。
けっこう極めてきた。

まずWikipediaにもあるアルゴリズムでnが整数のn乗根を実装した。
これで「小数の1/n乗（小数のn乗根)」が出来る。
ここがスタートライン。

XのY乗におけるYを1/nと考えるのが上記のn乗根だが、
そこをYがm/nとするように作り変える。(mもnも整数)
なんのことはない、Xのm乗をn乗根するだけだ。
Xの桁数が多かったり、mやnの数が多いと少し重たくなるかも知れない。
これで「小数の分数乗」が出来る。

次にXのY乗をm/nと考えるのではなく、
java.math.BigDecimalのような任意精度の小数を受け付けるようにした。
これのアルゴリズムは独自。
Yを1桁ずつに分解するという手法をとる。
Y=Y0.Y1Y2Y3〜Ynと考える。
Y0は整数部、Y1〜Ynはそれぞれが1桁の数字。

数式は以下のようになる。
X**Y=(X**(Y0*(10**0))) * (X**(Y1*(10**-1))) * (X**(Y2*(10**-2))) * (X**(Y3*(10**-3))) * ... * (X**(Yn*(10**-n)))

「小数の小数乗」は、「小数の分数乗をn+1個やって乗算」していく形になった。
ただし、これだけではダメだ。性能が出ない。
分数の分母部分が大きいとn乗根のアルゴリズムの中でn-1乗する箇所にコストがかかる。
そういうわけでさらに数式を分解した。
（m乗に関する部分は最大でも9乗になっているので既に安定してる。）

X**Y={X**(Y0*(10**0))} * {X**(Y1*(10**-1))} * {X**(Y2*(10**-1))}**(10**-1) * {{X**(Y3*(10**-1))}**(10**-1))}**(10**-1)) * ... * {{{(X**(Yn*(10**-1))}**(10**-1)}**...}**(10**-1)
注）10√の記号がネストしまくる状態です。

違いが分かりにくいだろうけれど、「小数の分数乗を複数回10乗根した後に乗算する」という形式だ。
これによって裏で大活躍するn乗根のアルゴリズムにおけるn-1乗部分は、
必ず9乗となり小数点以下の桁数が多いと爆発的に遅くなるという状態は回避された。

このアルゴリズムはどれだけ正確な値をもたらすかは作った自分でもよく分かっていない。
始めに心配したのは、1桁ごとに計算するので誤差が少しずつ混ざってやばいことにならないかということだった。
各桁ごとに計算しているのだが、その結果が持っている有効桁の範囲がそれぞれ違うので、
最後に掛け合せていくことで基本的に誤差はどんどん小さくなるようだ。
もっと数字を伴った話をすると、DECIMAL128の場合では、３４桁の結果を持っている数字を３４回近く乗算することになるので、約１１５６桁まで実は求めてるようなものだ。

持ってる桁数が中途半端な数字であると、誤差が小さくなりきれないことがあるかもしれない。
それは仕方が無いから裏の処理で用いる精度を水増しすることで乗り切れる。

ふぅ、余は満足じゃ。