第196回 ユークリッドの互除法(後編)

「ユークリッドの互除法、どんなふうにしたら《全体像》が見えるんでしょうか?」とテトラちゃんは首をかしげる。「整数に誘われて」シーズン第3章後編。
登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。好奇心旺盛で根気強い《元気少女》。

ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\LCM}[2]{\text{LCM}(#1,#2)} \newcommand{\gcdmath}[2]{\text{gcd}(#1,#2)} \newcommand{\GCD}[2]{\text{GCD}(#1,#2)} \newcommand{\XGCD}[2]{\text{XGCD}(#1,#2)} \newcommand{\EUCLID}[2]{\text{EUCLID}(#1,#2)} \newcommand{\EUCLIDLOOP}[2]{\text{EUCLID-LOOP}(#1,#2)} \newcommand{\ABS}[1]{\bigl|#1\bigr|} \newcommand{\SETL}{\bigl\{} \newcommand{\SETM}{\bigm|} \newcommand{\SETR}{\bigr\}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} $

ユークリッドの互除法

テトラちゃんリサの三人はユークリッドの互除法についておしゃべりをしている。 リサは、こんなアルゴリズムを見せた。
ユークリッドの互除法

入力
  • 非負整数$m$と正の整数$n$
出力
  • $m$と$n$の最大公約数
手続き

リサユークリッドの互除法

「そうか、そうか。これだけでいいわけだ!」

テトラ「ええ? こんなに短くなってしまうんですか? ほんとにこれで$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 = 4, n = 6$で考え、
  •  あたしは$m = 2, n = 4$で考え、
  •   リサちゃんは$m = 0, n = 2$で考えました。
  •   リサちゃんは$n$の値$2$をあたしに返して、
  •  あたしは$2$をそのまま先輩に返して、
  • その$2$がそのまま先輩の計算結果になりました。

リサ「末尾再帰可能」

「《繰り返し》があるね」

リサ「ループに展開」

テトラ「ループ?」

リサは、テトラちゃんの疑問には何も言わず、ぱたぱたとタイプした。 いや、《ぱたぱた》なんて音はしない。強いていえば、スッ……かな。

リサ「できた」

ユークリッドの互除法(ループ版)

入力
  • 非負整数$m$と正の整数$n$
出力
  • $m$と$n$の最大公約数
手続き

「……なるほどね」

テトラ「……これは、$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$座標が最大公約数」

リサ「できた」

リサは、僕たちにコンピュータのディスプレイを見せた。
この続きは有料会員登録をすると
読むことができます。
cakes・note会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

dearsip 前回の秘密ノート、このまま葉序の話にできそう 6ヶ月前 replyretweetfavorite

chibio6 2つの整数の最大公約数を求める計算回数を一つ増やすには、その整数同士を足せばいいとわかるのでフィボナッチは納得。わかりやすい説明に感謝。 6ヶ月前 replyretweetfavorite

je6bmq マジかーという感想 6ヶ月前 replyretweetfavorite

canaan1008 |結城浩 @hyuki |数学ガールの秘密ノート ホェーって声が出た https://t.co/FaKO7puKhT 6ヶ月前 replyretweetfavorite