「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。今月(2022年10月)からは多忙につき、日々の投稿数を減らします。

MENU

Pythonで学ぶアルゴリズム(16/18)

 アルゴリズムを学ぶのにPythonの学習も兼ねて

を参照していく。

9. 乱択アルゴリズムと数論

 実行の一部にランダムな挙動を含むアルゴリズム乱択アルゴリズムという。乱択アルゴリズムを扱うと効率的な解法をもたらすような問題が存在する。

9.1 アルゴリズムと乱数

 いくつかの選択から正解を選ぶテストにおいて、正しい思考の末に正解を導いたのか、もしくは運で回答したかは区別できない。そこで運により選択することをアルゴリズムに応用することを考える。

9.1.1 乱択アルゴリズムの例:クイックソート

 アルゴリズムの途中で乱数を用いてその後の振る舞いを変える計算方法乱択アルゴリズムという。クイックソート乱択アルゴリズムの一種である。

9.1.2 乱択アルゴリズムの種類
   モンテカルロアルゴリズム 乱数によっては結果が誤りになり得る乱択アルゴリズム
   ラスベガス・アルゴリズム 乱数にかかわらず結果が常に正しい乱択アルゴリズム
9.1.3 例:面接試験

 二択で答えられる質問を何度も質問して面接相手を有望な人材かを選別することを考える。もし目の前に将来有望な人材が現われた場合、南海質問しても優れた回答が返ってくるためこの人物に対する評価は確信に変わり得る。普通の人材が優れた回答をする確率が\displaystyle{\frac{1}{4}}だとすれば、何度も質問を重ねることで有望な人材をあ


9.2 数論

 数学の一分野である数論はアルゴリズムと相性が良い。数論の例に触れながら、アルゴリズムを紹介する。

9.2.1 合同式

 性数に話を限定し、さらに剰余を考えることにする。ある整数a,bについてある整数mで割ったときの剰余が等しいとき、



\begin{aligned}
a\equiv b\ \ \ \ (\mathrm{mod}\ m)
\end{aligned}


で表現する。これを合同式という。abmを法として等しい(合同である)という。
 a\equiv b\ \ \ \ (\mathrm{mod}\ m)かつc\equiv d\ \ \ \ (\mathrm{mod}\ m)であるとき、



\begin{aligned}
a+c&\equiv b+d\ \ \ \ (\mathrm{mod}\ m)\\
a-c&\equiv b-d\ \ \ \ (\mathrm{mod}\ m)\\
ac&\equiv bd\ \ \ \ (\mathrm{mod}\ m)\\
ka&\equiv kb\ \ \ \ (\mathrm{mod}\ m),k\in\mathbb{Z}
\end{aligned}


が成り立つ。

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)


 すなわちa,p\in\mathbb{N}について



\begin{aligned}
a^{p-1}\equiv 1\ \ (\mathrm{mod}\ p)
\end{aligned}


が成り立つ。これを\mathrm{Fermat}の小定理という。

9.2.3 冪乗と余り

 一般にa^k,a\in\mathbb{N}素数とは限らないm\in\mathbb{N}で割った余りを計算したいとする。kが非常に大きいとまともには計算できない。そこでこれを効率的に解くべく繰り返し二乗法を用いる。
 たとえば7^{43}123で割った余りを求めたいとする。ここで43を二進数展開する。すなわち



\begin{aligned}
43&=1\times2^5+0\times2^4+1\times2^3+0\times2^2+1\times2^1+1\times2^0\\
&=32+0+8+0+2+1
\end{aligned}


である。したがって



\begin{aligned}
7^{43}=7^{32}\times7^{8}\times7^{2}\times7^{1}
\end{aligned}


を得る。ここに\mathrm{Fermat}の小定理を用いれば

   7^1 = 7 \equiv 7\ (\mathrm{mod}\ 123)
   7^2 = 49 \equiv 49\ (\mathrm{mod}\ 123)
   7^4 = 49^2 \equiv 64\ (\mathrm{mod}\ 123)
   7^8 = 64^2 \equiv 37\ (\mathrm{mod}\ 123)
   7^{16} = 37^2 \equiv 16\ (\mathrm{mod}\ 123)
   7^{32} = 16^2 \equiv 10\ (\mathrm{mod}\ 123)

となるから、



\begin{aligned}
7^{43}&=7^{32}\times7^{8}\times7^{2}\times7^{1}\\
&\equiv10\times37\times49\times7\equiv97\ (\mathrm{mod}\ 123)
\end{aligned}


を得る。以上をアルゴリズムに落とし込むことで効率的に余りを求めることができる:

入力をa,k,mとする。

(1) b=1とする。
(2) kの二進数表現を得て一番下の位から順に[texi]に格納し(3),(4)を繰り返す。
(3) i=1ならばabmで割った余りをbとして更新する。そうでなければ(4)に移る。
(4) aを二乗してmで割った余りでaを更新する。
(5) bを出力する。
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)
プライバシーポリシー お問い合わせ