![[logo]](https://img.hyuki.net/20220628121544-7a397ed015277339.png)
Web連載「数学ガールの秘密ノート」
登場人物紹介
僕：数学が好きな高校生。
テトラちゃん：僕の後輩。好奇心旺盛で根気強い《元気少女》。
ミルカさん：数学が好きな高校生。僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ：自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
僕、テトラちゃん、リサの三人はユークリッドの互除法についておしゃべりをしている。 リサは、こんなアルゴリズムを見せた。
ユークリッドの互除法
入力
リサ「ユークリッドの互除法」
僕「そうか、そうか。これだけでいいわけだ！」
テトラ「ええ？ こんなに短くなってしまうんですか？ ほんとにこれで $m$ と $n$ の最大公約数が……」
僕「うん、うまくいくねえ…… 具体的に $m = 4, n = 6$ でやってみよう！」
リサ「ウォークスルー」
僕「$m = 4, n = 6$ からスタートだよ」
僕（$m = 4, n = 6$）
E1: $\EUCLID{4}{6}$ を計算しよう。
E2: $4 > 0$ だから、E3へ進む。
E3: $\EUCLID{6 \bmod 4}{4}$ つまり $\EUCLID{2}{4}$ を計算して出力しよう。
僕「ここまでで、 $\EUCLID{4}{6}$ の値は、 $\EUCLID{2}{4}$ を計算すればいいということがわかった」
テトラ「はい、ここで気持ちも新たに $\EUCLID{2}{4}$ を計算します」
テトラ（$m = 2, n = 4$）
E1: $\EUCLID{2}{4}$ を計算しましょう。
E2: $2 > 0$ ですから、E3へ進みますね。
E3: $\EUCLID{4 \bmod 2}{2}$ つまり $\EUCLID{0}{2}$ を計算して出力しましょう。
テトラ「ですからここまでで、 $\EUCLID{2}{4}$ の値は、 $\EUCLID{0}{2}$ を計算すればいいということがわかりましたっ！」
リサ「再帰呼び出しで $\EUCLID{0}{2}$」
リサ（$m = 0, n = 2$）
E1: $\EUCLID{0}{2}$ を計算開始。
E2: $0 > 0$ ではないから、E4へ。（咳）
E4: E5へ。
E5: 出力は $2$（$\EUCLID{0}{2}$）。
リサ「$2$」
テトラ「リサちゃんの $2$ は $\EUCLID{0}{2}$ の計算結果ですから、それが $\EUCLID{2}{4}$ の値となります。 先輩、 $2$ です。はいっ！」
テトラちゃんは、そういって、僕にボールを返す仕草をする。このボールは $\EUCLID{2}{4}$ の値なんだな。
僕「いまテトラちゃんが渡してくれた $2$ は $\EUCLID{2}{4}$ の計算結果ということで、 それが $\EUCLID{4}{6}$ の値になる、と。確かにそれは、 $4$ と $6$ の最大公約数 $2$ に等しくなっているね」
リサ「計算終了」
テトラ「そうですね。具体的な値で計算すると《繰り返し》がよくわかります。 ほんとに《例示は理解の試金石》ですね。
リサ「末尾再帰可能」
僕「《繰り返し》があるね」
リサ「ループに展開」
テトラ「ループ？」
リサは、テトラちゃんの疑問には何も言わず、ぱたぱたとタイプした。 いや、《ぱたぱた》なんて音はしない。強いていえば、スッ……かな。
リサ「できた」
ユークリッドの互除法（ループ版）
入力
僕「……なるほどね」
テトラ「……これは、 $m > 0$ の間、L3,L4,L5を《繰り返し》て計算するということでしょうか」
リサ「L2に来るたび、 $m > 0$ 確認（咳）」
テトラ「？」
僕「L5で $m$ の値が変化して、L6からL2に戻り、そこで改めて $m > 0$ かどうかを調べるってことだね」
テトラ「やっぱり、きちんと確かめたいですね……」
リサ「ウォークスルー」
（$m = 4, n = 6$）
L1: $\EUCLIDLOOP{4}{6}$ を計算します。
L2: $4 > 0$ だから、L3へ進みます。
L3: $n \bmod m = 6 \bmod 4$ の値、つまり $2$ を、 $r$ に代入します（$r = 2$ になりました）。
L4: $m$ の値、つまり $4$ を、 $n$ に代入します（$n = 4$ になりました）。
L5: $r$ の値、つまり $2$ を、 $m$ に代入します（$m = 2$ になりました）。
L6: L2へ戻ります。
（この時点で $m = 2, n = 4$ です。うまくいきそうですね）
L2: $2 > 0$ だから、L3へ進みます。
L3: $n \bmod m = 4 \bmod 2$ の値、つまり $0$ を、 $r$ に代入します（$r = 0$ になりました）。
L4: $m$ の値、つまり $2$ を、 $n$ に代入します（$n = 2$ になりました）。
L5: $r$ の値、つまり $0$ を、 $m$ に代入します（$m = 0$ になりました）。
L6: L2へ戻ります。
（この時点で $m = 0, n = 2$ です。大丈夫ですね！）
L2: $0 > 0$ ではないので、L7へ進みます。
L7: $n$ の値、つまり $2$ を、 $\EUCLIDLOOP{4}{6}$ の結果として出力して、この手続きを終了します。
僕「なるほど、よくわかるね」
テトラ「先ほどの $\EUCLID{4}{6}$ では、先輩→あたし→リサちゃんというボールを渡して《繰り返し》ていたのが、 $\EUCLIDLOOP{4}{6}$ では、whileの《繰り返し》になっているんですね」
僕「これで、最大公約数を求める《ユークリッドの互除法》をすっきり理解した……というところかな」
テトラ「そうですねっ！ あ、でも一つだけ気になることが」
僕「え？」
テトラ「はい。あのですね、アルゴリズムをウォークスルーするときには、一歩一歩進みますよね」
僕「そうだね。だからこそよくわかるんだけど。証明みたいだ」
テトラ「そ、そうなんですが、あたしはもっと《全体像》が見たいです」
僕「全体像？ テトラちゃんがよく言う《旅の地図》ってこと？」
テトラ「そうですね。『ああ、あたしたちは、こんなところを通ってきたんだな。 最大公約数を求めるために、こういうことをしてきたんだな』というのを一望できるような……す、すみません。 なんだか勝手なことを」
リサ「きゃうんっ！」
急にリサが子犬のような声をあげる。 見ると、いつのまにか現れたミルカさんが、 リサの赤い髪をもしゃもしゃといじっていた。
ミルカ「今日はユークリッドの互除法？」
リサの抵抗にあって髪をもてあそぶのをやめたミルカさんは、 ディスプレイに表示されているアルゴリズムを眺めながらそう言った。
テトラ「そうです。さっきからウォークスルーをしていたんですが……」
僕「《全体像》を見たいという話をしていたんだよ、ミルカさん」
ミルカ「全体像」
テトラ「はい……」
ミルカ「$\EUCLID{m}{n}$ でも、 $\EUCLIDLOOP{m}{n}$ でも同じだが、 $m$ と $n$ の二つの数が絡み合いながら計算は進んでいく。 二つの数が絡み合いながら進む《全体像》を見たいとしたら、 素朴に考えると……」
テトラ「素朴に考えると？」
僕「そうか、座標平面か！ 平面上の点 $(m,n)$ がどう動くかを見るということだね？」
ミルカ「たとえば、そういうこと」
リサ「……」
テトラ「なるほどです……アルゴリズムが進むにつれて、 $m$ と $n$ は変化します。ということは、点が移動する……座標平面の右上から左下へ向かって点が進むことになりますね？」
僕「$\EUCLID{4}{6}$ だと、 $$ (4,6) \to (2, 4) \to (0, 2) $$ という動きになるよね。 そして、 $(0,n)$ という形になったとき最大公約数は $n$ となってアルゴリズムは停止するんだから、 《点が $n$ 軸上に達すること》がアルゴリズム停止の条件で、そのときの $n$ 座標が最大公約数」
リサ「できた」
リサは、僕たちにコンピュータのディスプレイを見せた。
無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。
ひと月500円で「読み放題プラン」へご参加いただきますと、 420本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方／すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加（2017年5月26日）
![[icon]](https://img.hyuki.net/20220619121014-abd58cfc2ab436f4.png)