高速冪乗法
一般にa^{2^k}の計算は
普通に計算すれば2^k-1回
高速冪乗法を使えばk回で済む
例えば3^{32}を素朴に計算すると
3\times3\times\cdots\times3というふうに31回計算する必要があるが、
((((3^2)^2)^2)^2)^2と計算すれば5回ですむ
a^xを求める手順
xを2進数表示する→(x_{k-1},x_{k-2},\cdots,x_0)_2
つまりx=x_{0}+2 x_{1}+2^{2} x_{2}+\cdots+2^{k-1} x_{k-1}
なのでa^xは以下のように書ける
a^{x}=a^{x_{0}+2 x_{1}+2^{2} x_{2}+\cdots+2^{k-1} x_{k-1}}=a^{x_{0}}\times\left(a^{2}\right)^{x_{1}} \times\left(a^{2^{2}}\right)^{x_{2}} \times \cdots \times\left(a^{2^{k-1}}\right)^{x_{k-1}}
最初の等号はxを上の「つまり」の式に変えているだけ
本質は最右辺
a^{2^k}の使い回しだけで計算できている
nbpower[a_, 0] := 1
power[a_, n_ /; EvenQ[n]] := power[a*a, (Quotient[n, 2])]
power[a_, n_ /; OddQ[n]] := a*power[a, (n - 1)]
FPower[a_, n_, m_] := Mod[power[a, n], m]
関連
参考
Haskellで記述
わざわざ2進数に変換する必要がないことがわかる