を参照していく。
9. 乱択アルゴリズムと数論
実行の一部にランダムな挙動を含むアルゴリズムを乱択アルゴリズムという。乱択アルゴリズムを扱うと効率的な解法をもたらすような問題が存在する。
9.1 アルゴリズムと乱数
いくつかの選択から正解を選ぶテストにおいて、正しい思考の末に正解を導いたのか、もしくは運で回答したかは区別できない。そこで運により選択することをアルゴリズムに応用することを考える。
9.1.3 例:面接試験
二択で答えられる質問を何度も質問して面接相手を有望な人材かを選別することを考える。もし目の前に将来有望な人材が現われた場合、南海質問しても優れた回答が返ってくるためこの人物に対する評価は確信に変わり得る。普通の人材が優れた回答をする確率がだとすれば、何度も質問を重ねることで有望な人材をあ
9.2 数論
数学の一分野である数論はアルゴリズムと相性が良い。数論の例に触れながら、アルゴリズムを紹介する。
9.2.1 合同式
性数に話を限定し、さらに剰余を考えることにする。ある整数についてある整数
で割ったときの剰余が等しいとき、
で表現する。これを合同式という。と
は
を法として等しい(合同である)という。
かつ
であるとき、
が成り立つ。
9.2.2 フェルマーの小定理
合同式を持ち出すと興味深い結果が得られる。
print('a\ta%3') for a in range(10): print('{}\t{}'.format(a, a%3)) ############## m = 3 " 3も自分のスペースを用意して右に詰めるテンプレートを用意" tmpl = '{:>3}' * 5 print(tmpl.format('a', 1, 2, 3, 4)) for a in range(m): print(tmpl.format(a, a % m, a**2 % m, a**3 % m, a**4 % m)) ############## def make_table(m): tmpl = '{:>5}' * (m+2) header = ['a'] for i in range(1, m+2): header.append(i) print(tmpl.format(*header)) for a in range(m): vals = [a] for i in range(1, m+2): vals.append(a**i % m) print(tmpl.format(*vals)) make_table(5)
すなわちについて
が成り立つ。これをの小定理という。
9.2.3 冪乗と余り
一般にを素数とは限らない
で割った余りを計算したいとする。
が非常に大きいとまともには計算できない。そこでこれを効率的に解くべく繰り返し二乗法を用いる。
たとえばを
で割った余りを求めたいとする。ここで
を二進数展開する。すなわち
である。したがって
を得る。ここにの小定理を用いれば
となるから、
を得る。以上をアルゴリズムに落とし込むことで効率的に余りを求めることができる:
入力を
とする。
(1) とする。
(2) の二進数表現を得て一番下の位から順に[texi]に格納し(3),(4)を繰り返す。
(3) ならば
を
で割った余りを
として更新する。そうでなければ(4)に移る。
(4) を二乗して
で割った余りで
を更新する。
(5) を出力する。
def a_m_mod_m(a, k, m): b = 1 for i in reversed(bin(k)[2:]): if i=='1': b = a * b % m a = a**2 % m return b a_m_mod_m(7, 43, 123)