はじめに
こんにちは！今回は分割統治法(Divide and Conquer)と動的計画法(Dynamic Programming)を組み合わせて、効率的にべき乗を計算しうるモジュラー指数法(Modular Exponentiation)をPythonで実装する方法を紹介します。
モジュラー指数法は次の形の計算を効率よく行うアルゴリズムです。
base^exp % mod (baseのexp乗をmodで割った余り)
この記事で紹介する内容
- 分割統治法を利用したアルゴリズムの概要
- 動的計画法を活用した効率的な計算
- Pythonのコード実装とっその解説
- 実行例
モジュラー指数法とは？
べき乗の計算は指数が大きくなると非常に計算コストがかかります。例えば、673^283 % 713のような計算を直接行うと、桁数が膨大となりメモリや処理速度が大きく影響を受けます。これを効率よく処理するのがモジュラー指数法です。分割統治法を用いることで計算量を減らし、指数計算の負担を軽減します。
実装コード
以下がPythonで実装したコードです。
def mod_exp(base, exp, mod):
"""効率的なモジュラー指数法を用いて base^exp % mod を計算する関数"""
result = 1
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
base = (base * base) % mod
exp //= 2
return result
# ユーザ入力
base = int(input("基数（base）を入力してください: "))
exp = int(input("指数（exp）を入力してください: "))
mod = int(input("モジュロ（mod）を入力してください: "))
# それぞれの値を計算
P8 = mod_exp(base, 2, mod)
P7 = (P8 * P8) % mod
P6 = (P7 * P7) % mod
P5 = (base * P6 * P6) % mod
P4 = (base * P5 * P5) % mod
P3 = (P4 * P4) % mod
P2 = (base * P3 * P3) % mod
P1 = (base * P2 * P2) % mod
# 結果の出力
print("(1) P8 の値:", P8)
print("(2) P7 の値:", P7)
print("(3) P6 の値:", P6)
print("(4) P5 の値:", P5)
print("(5) P4 の値:", P4)
print("(6) P3 の値:", P3)
print("(7) P2 の値:", P2)
print("(8) P1 の値:", P1)
アルゴリズム解説
モジュラー指数法(分割統治法)
このプログラムでは指数の計算を指数を半分に分割しながら行っています。例えば、base^8を計算する際にbase^4を2回掛ける形にすれば、計算量が大幅に減ります。また、偶数・奇数の処理に応じて計算結果を更新しながら最終的な答えを得ます。
動的計画法(Dynamic Programming)
同じ計算を繰り返さないように、既に計算した値を再利用しています。P8の計算結果を使ってP7を計算するなど、動的計画法の考え方を活用することで無駄な処理を省いています。
実行例
次のような入力をした場合の実行結果を示します。
基数（base）を入力してください: 673
指数（exp）を入力してください: 283
モジュロ（mod）を入力してください: 713
(1) P8 の値: 174
(2) P7 の値: 330
(3) P6 の値: 524
(4) P5 の値: 12
(5) P4 の値: 657
(6) P3 の値: 284
(7) P2 の値: 85
(8) P1 の値: 478
まとめ
モジュラー指数法を使えば、指数が大きな計算でも高速に結果を求めることができます。今回の実装では動的計画法を組み合わせることで、さらに効率を向上させました。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！