二つの数の最大公約数を求めたい

二つの数の最大公約数を求める方法についてまとめます. そもそも最大公約数というのは、ある数a,bがあるときに最大公約数はaを割り切れてbも割り切れる最大の数です. それを求める方法について以下3つ紹介します. ・素因数分解から求める 　　最大公約数がどの数にも含まれる約数を掛け合わせた最大であることを利用して、最大公約数を求めます.素因数分解を初めにするため、プログラミングでは計算に時間がかかり、適用できない手法です. ・ユークリッド互助法 アルゴリズムの形で最大公約数を見つけ出す代表的な手法.プログラミング等ではこれらが用いられる. ・拡張ユークリッド互助法 「ax+by=最大公約数」でx,y,最大公約数を求める問題を解くことで最大公約数を求められる方法.どんなときにもx,yが存在することは保証されている. ・バイナリGCDアルゴリズム 　　シフト演算などを用いることをメインとしたアルゴリズムで、ユークリッド互助法や拡張ユークリッド互助法より効率がよいとされるケースがある.

$$a = 2^5 \times 3^4 \times 5^3 \times 7^0$$ $$b = 2^{10} \times 3^0 \times 5^2 \times 7^w$$

ここでは最も分かりやすい素直な方法によって最大公約数を求めます. 最大公約数はaとbの公約数を全て列挙すればそれの共通であり最大を書き出せば求まるはずです. 全て列挙するのは大変なので、a(2が5個)からもb(2が10個)からも持ってこれる最大の約数の数(10個)をそれぞれの約数で決めてしまう方法で行います. つまり例えば上の例なら,aは2を5個、bは2を10個持っているので、最大でも2は5個分しか共通でもてていないのでそれが2の約数で構成される最大の数です.3はbが、7はaが持っていないのでスキップします.そして残るは5ですが、少なくとも2個aもbも持っているので、2を5個と7を2個を共通に持っていることが分かり,これらを掛け合わせた数が最大公約数です.

ここでは手順として、 1. 素因数分解して、各約数ごとの個数を数える 2. それらの約数で共通に持っている数を求めて掛け合わせる を行っています. 人間にとって1はとても簡単ですが、パソコンにとっては素因数分解は少しだけ面倒くさい計算をしなくてはなりません.そのため通常プログラミングおいてこの算出方法は用いず、次のユークリッド互助法を用います.

ユークリッド互助法の詳しい説明はここでは控えます.簡単に紹介するとaとbが与えられたときにaとbが共通に持っている約数はaとbと|a-b|も共通に持っているということを前提にして計算を楽にしていきます. aとbの約数は|a-b|とaの約数で、それはまた|a-|a-b||と|a-b|の約数で...と最後に0になるまで計算続ける方法です.

15と24の場合 $$ 24 = 15 + 9$$ (24と15の約数は15と9も約数として持つ) $$ 15 = 9 + 6$$ (15と9の約数は9と6も約数として持つ) $$ 9 = 6 + 3 $$ (9と6の約数は6と3も約数として持つ) $$ 6 = 3 + 3$$ (6は3で割り切れる)

拡張ユークリッド互助法は ax+by=(最大公約数)に当てはまる値を求めることで、最大公約数を求めることができるアルゴリズムです.このアルゴリズムはよく使用されます.

a,b が与えられているときに, $$q _i= r_{i-1 }/ r_i $$ $$r_{i+1} = r_{i-1 } - r_i q_i $$ $$s_{i+1} = s_{i-1 } - s_i q_i $$ $$t_{i+1} = t_{i-1 } - t_i q_i $$ で更新を行っていき,\(r\)が0になったときに停止します.

バイナリGCDアルゴリズム(Binary GCD Algorythm)はプログラミングを意識してシフト演算などを多く入れたユークリッド互助法の改良版です.ハードウェアにもよりますが、ユークリッド互助法より良くなるケースがあります.

バイナリGCDアルゴリズムについて概要のみ紹介します. これはa,bが偶数かそうでないかを意識しながら以下のように処理を行っていきます.大方ユークリッド互助法と同様のことを行っています. 手順 ・もしaもbも偶数. 2で割る(1bit右シフト) ・もし片方偶数なら、偶数の方を2で割る. ・もし双方奇数なら、a-bは偶数になるので、|a-b|/2と(a,bの小さい方)として処理を続けます. 上記を繰り返して二つの数字の組の片方が0になったときに処理を停止します.