繰り返し自乗法
概要
の値を効率的に解きます。
使える状況
「をで割ったあまり」が欲しいときに、があまりにも大きいとその計算だけで時間がかかってしまうことがあります。そのような時には、この繰り返し自乗法を用いることで素早く求めることが出来ます。
説明
の値を求めたいとき、愚直な方法として次のような手法を考えることが出来ます。
using ll = long long int; ll PowMod(ll N, ll P, ll M){ ll ans = 1; for(ll i=0; i<P; ++i){ ans *= N; ans %= M; } return ans; }
しかし、上記のような方法だと回ループしてしまうため、などの場合では非常に時間がかかってしまいます。
そこで使うのが、繰り返し自乗法です。
繰り返し自乗法は、
「を一回一回掛けてmodを取るのでは時間がかかるので、まとめて掛けてしまおう!」
という考えをもとにしたアルゴリズムです。
この「まとめて掛ける」というのがどういうことか、具体的にのときについて考えながら説明します。
以下、求める値を、とし、また、""の計算をした時にはで割った余りを求める操作も一緒に行っているものとします。
ボトムアップ(小さい値から大きい値へと計算していく)な考え方
先ほどの愚直な方法では、次のような計算をしていることになります。
確かに、回、つまり回分の計算をしていることがわかりますね。
ここで、上で計算しているように、
となっていることから、
とまとめてしまい、あとは、
と出来るので、計算回数は最初のを計算する回と、まとめた後の回となっているので、見事に半分にすることが出来ていますね。
これをさらに、
とすることによりを求め、同様にを求め、…と繰り返すことで、最終的には
とまで式を短くすることが出来ます。
このとき、次の回しか計算をしていないことが分かりますね。
- を求める()
- を求める()
- を求める()
- を求める()
- を求める()
このように、の自乗を繰り返し計算した結果を用いて計算を行っているので、「繰り返し自乗法」と言うんですね。
コード(C++)
using ll = long long int; ll RepeatSquaring(ll N, ll P, ll M){ if(P==0) return 1; if(P%2==0){ ll t = RepeatSquaring(N, P/2, M); return t*t % M; } return N * RepeatSquaring(N, P-1, M); }
コードの説明
トップダウンな考え方の節で示した式を、そのまま関数に落とし込んでいるだけです。
具体例
の値を求める。
今回は、愚直な方法(関数PowMod_Simple)と繰り返し自乗法(PowMod_RepeatSquaring)でどのくらい性能の差があるかを、
の2点について見てみます。
#include <iostream> #include <algorithm> #include <chrono> using ll = long long int; ll count_ps = 0; ll PowMod_Simple(ll N, ll P, ll M){ ll ans = 1; for(ll i=0; i<P; ++i){ ++count_ps; ans *= N; ans %= M; } return ans; } ll count_prs = 0; ll PowMod_RepeatSquaring(ll N, ll P, ll M){ ++count_prs; if(P==0) return 1; if(P%2==0){ ll t = PowMod_RepeatSquaring(N, P/2, M); return t*t % M; } return N * PowMod_RepeatSquaring(N, P-1, M); } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); //愚直な方法----------------------------- std::cout << "愚直な方法\n"; auto startTime = std::chrono::system_clock::now(); //処理部------ std::cout << "2^1000000000 mod 1000000007 = " << PowMod_Simple(2, 1000000000, 1000000007) << "\n"; std::cout << "再帰回数\t:" << count_ps << "\n"; //------------ auto endTime = std::chrono::system_clock::now(); std::cout << "処理時間:" << std::chrono::duration_cast<std::chrono::nanoseconds>(endTime - startTime).count() << "ns\n"; //--------------------------------------- std::cout << "------\n"; //愚直な方法----------------------------- std::cout << "繰り返し自乗法\n"; startTime = std::chrono::system_clock::now(); //処理部------ std::cout << "2^1000000000 mod 1000000007 = " << PowMod_RepeatSquaring(2, 1000000000, 1000000007) << "\n"; std::cout << "再帰回数\t:" << count_prs << "\n"; //------------ endTime = std::chrono::system_clock::now(); std::cout << "処理時間:" << std::chrono::duration_cast<std::chrono::nanoseconds>(endTime - startTime).count() << "ns\n"; //--------------------------------------- return 0; }
実行結果(一例)
愚直な方法 2^1000000000 mod 1000000007 = 140625001 再帰回数 :1000000000 処理時間 :22322817871ns ------ 繰り返し自乗法 2^1000000000 mod 1000000007 = 140625001 再帰回数 :43 処理時間 :2709ns
この結果からも分かるように、再帰回数、処理時間ともに、文字通り桁違いで小さく計算することが出来ていますね。
ちなみに、処理時間の「ns」は「ナノ秒(ナノ)」を表しているため、
- 愚直な方法 :22.322817871秒
- 繰り返し自乗法 : 0.000002709秒
の時間がかかっていることを表しています。
備考
愚直な方法は計算量がであるのに対し、繰り返し自乗法ではにまで抑えられています。