情報数学1 第1-2章 - Tominaga Lab, Chausson

情報数学1 第1-2章
最大公約数とユークリッドの互除法
香川大学工学部 富永浩之
[email protected]
概
要
■ 最大公約数の性質
整除関係
互いに素
公約数
公倍数
GCD
LCM
■ ユークリッドの互除法の漸化式と計算過程
gcd(a,b)
初期条件
漸化式
■ 互除法の剰余列とアルゴリズム
剰余列
機械性と停止性
手続と算法
■ 互除法の効率性と最小剰余による改良
最小剰余
■ 互除法の図形的意味とブレントの算法
二コマコスの算法
ブレントの算法
第01節 [1] 公約数と公倍数
6の約数
6の倍数
±1, ±2, ±3, ±6
0, ±6, ±12, ±18, ‥
12と18の公約数
10と15の公倍数
最大公約数
最小公倍数
1は全ての約数
0は全ての倍数
1, 2, 3, 6
0, 30, 60, 90, ‥
GCD [Greatest Common Divisor]
gcd(a,b) gcd(12,18)=6
LCM [Least Common Multiple]
lcm(a,b) lcm(10,15)=30
・ 約数と倍数は符号付で考えることがある
・ 公約数の約数は公約数、公倍数の倍数は公倍数
第01節 [2] 整除関係と互いに素
整除関係
a|b
bがaで割り切れる
aがbの約数、bがaの倍数
整除系列
a≪b
整除関係を順序として表記
1≪3≪6≪12≪0
互いに素
a⊥b aとbのGCDが1
整数の性質を調べる上での基本の場合
余因数
a,bに対し、GCDで割った整商
gcd(a,b)=d とおくと a’=a/d, b’=b/d
a=a’d, b=b’d かつ a’⊥b’
整数の様々な性質の証明に用いる
第02節 [1] 最大公約数の性質
<1>
<2>
gcd(a,b) = gcd(b,a)
gcd(-a,b) = gcd(a,b)
交換律
符号無視
<3>
<4>
gcd(a,1) = 1
gcd(a,0) = a
1は全ての約数
0は全ての倍数 (a>0)
<5> gcd(ka,kb) = k×gcd(a,b)
<5>’ gcd(ab,b) = b
共通因数の括出し (k>0)
整除関係 (b>0)
<6> gcd(a,b) = gcd(a-b,b)
<6>’ gcd(a,b) = gcd(a%b,b)
差への還元
剰余への還元 (b≠0)
<5>
<6>
gcd(42,30)=gcd(6×7,6×5)=6×gcd(7,5)=6×1=6
gcd(42,15)=gcd(27,15)=gcd(12,15)
=gcd(15,12)=gcd(3,12)=3
第02節 [2] 目の子の筆算によるGCDの計算
2 | 84 60
2 | 42 30
3 | 21 15
ーーーーーー
×
7
5
12
⊥
・
・
・
・
・
・
=
=
=
=
=
gcd(84,60)
gcd(42,30)×2
gcd(21,15)×2×2
gcd( 7, 5)×3×2×2
1×3×2×2
12
GCDの性質<5> 共通因数の括出し を利用している
筆算は、式変形の本質的な部分のみを抜き出している
目の子(人間の直感)で、共通因数を見つけている
小さい数には有効だが、大きい数には歯が立たない
機械的な処理手順ではないので、プログラムとして書きにくい
全ての数で順に割り切れるか調べる方法は、効率が非常に悪い
第03節 [1] 最小公倍数の性質
<1>
<2>
<3>
<4>
a⊥b のとき
余因数の括出し
共通因数の括出し
積の公式
lcm(a,b) = a×b
lcm(a,b) = a’×b’×gcd(a,b)
lcm(ka,kb) = k×lcm(a,b)
a×b = gcd(a,b)×lcm(a,b)
・ LCMは、2数の積をGCDで割って求めることができる
・ 実際の計算では、オーバーフローを防ぐため、
一方をGCDで割ってから、他方を掛ける
・ 正整数の組 a,b に対し、GCDとLCMの値が分かれば、
一方 a から他方 b が一意に求められる
第04節 [1] ユークリッドの互除法の定義
漸化式による、効率的なGCDの計算
古代ギリシャの数学者ユークリッドが発見(?)
世界最古の算法(アルゴリズム) ‥機械的な計算手順
gcd(a,b) = { a
{ gcd(b,a%b)
; b=0
; else
gcd(51,36)=gcd(36,15)=gcd(15,6)=gcd(6,3)=gcd(3,0)=3
gcd(3,5)=gcd(5,3)=gcd(3,2)=gcd(2,1)=gcd(1,0)=1
初期条件
漸化式
性質<4> gcd(a,0)=a より
性質<6>’ gcd(a,b)=gcd(a%b,b) より
性質<1> gcd(a%b,b)=gcd(b,a%b) より
第06節 [1] 互除法の図形的意味
gcd(8,6)=2
lcm(3,2)=6
8×6の長方形を覆う、
最大の正方形のタイルは
2×2 ⇒ GCD
3×2のタイルを並べて、
覆える最小の正方形は
6×6 ⇒ LCM
gcd(17,7)=gcd(7,3)=gcd(3,1)=1
長方形から最大サイズ
(短辺)の正方形を
取れるだけ除く ⇒ <6>’
縦横を置き換えて、
同様に繰り返す ⇒ <4>
残余がなくなれば、
そのサイズがGCD ⇒ <1>
第04節 [2] ユークリッドの互除法の計算過程
k
a
b
q
r
------------------------------
0
48 ÷ 34 = 1 ‥ 14
gcd(48,34)
1
34 ÷ 14 = 2 ‥
6
= gcd(34,14)
2
14 ÷
6 = 2 ‥
2
= gcd(14, 6)
3
6 ÷
2 = 3 ‥
0
= gcd( 6, 2)
4
2
0
= gcd( 2, 0)
------------------------------
4回の再帰呼出
= 2
第05節 [1] 互除法の剰余列
計算
剰余列
回
gcd(48,34)=gcd(34,14)=gcd(14,6)=gcd(6,2)=gcd(2,0)=2
48, 34, 14, 6, 2, 0
0で終わる有限の数列
34, 48, 34, 14, 6, 2, 0
a<b のときは b, a と入替え
0
1
2
1 20
1
1 20
3
2
3
4
5
0
4 20 11
9
2
1
0
2
0
3 20 12
8
4
0
3 20
3
2
4 20 13
7
6
1
1 20
4
0
3 20 14
6
2
0
1 20
5
0
2 20 15
5
0
2 20
6
2
0
2 20 16
4
0
3 20
7
6
1
4 20 17
3
2
2 20
8
4
0
2 20 18
2
0
3 20
9
2
1
2 20 19
1
0
1 20 10
0
1 20 20
0
0
0
0
5
回
1
1
4
0
1
0
0
第05節 [2] 互除法の剰余列の漸化式
gcd(a,b) の計算における剰余列 N(k) の定義
初期条件
漸化式
終了条件
N(0) = a, N(1) = b
; 与数
N(k) = N(k-2) % N(k-1) ; k≧2, N(k-1)>0
N(p+1) = 0
; 列長 p+2
剰余条件より
GCDの性質より
狭義単調減少 N(1)>N(2)>‥>N(p)>N(p+1)=0
gcd(a,b)=gcd( N(k), N(k+1) )=N(p)
while
t =
b =
a =
}
( b != 0 ) {
b;
a%b;
t;
n[0] = a; n[1] = b;
k = 1;
while ( n[k] != 0 ) {
k++;
n[k] = n[k-2] % n[k-1];
}
第05節 [2] アルゴリズムの条件
● 機械性 ‥ 手続 [procedure]
・ 個々の処理が厳密に定義されていて、機械的に実行できる
・ 同じ入力に対し、いつ誰が計算しても、同じ出力となる
● 停止性 ‥ 算法 [algorithm]
・ 有限な入力に対し、有限回のうちに手順が必ず終了する
・ 真の乱数は、アルゴリズムでは作れない(疑似乱数)
・ 機械的であるが止まらない手続が存在する(無限ループ)
・ 止まるか止まらないか未だに分からない手続きも存在する
■ 互除法がアルゴリズムであること
○ 機械性
○ 停止性
数学的な漸化式で定義されている
剰余列が狭義単調減少で必ず0で終了する
第06節 [2] 最小剰余による効率化
● 互除法の計算回数の最悪ケース
整商が1しか立たず、大きな剰余が残ると、計算が進まない
すなわち、 N(k)=N(k-1)%N(k-2)=N(k-1)-N(k-2) のとき
これは、フィボナッチ数列を逆順にした数列
● 互除法の漸化式を効率化
剰余列の次項を最小剰余で考え、性質<2>より符号無視
正剰余で次項が除数の1/2超のとき、最小剰余では1つ飛越し
正
最小
13, 8, 5, 3, 2, 1, 0
13, 8,
3,
1, 0
4回
2回
13 ÷ 8 = 1 ‥ +5
13 ÷ 8 = 2 ‥ -3
【例題】 621, 323, (298), 25, (23), 2, 1, 0
第07節 [1] ニコマコスの算法
● ニコマコスの算法
・
・
・
・
・
ユークリッドの互除法より以前に用いられた算法
a>b のとき gcd(a,b)=gcd(b, a-b) とする
負荷の高い除算の代わりに、減算を使った漸化式を考える
a,bの桁数が異なると、大量の減算が必要となり、効率的でない
除算の実装は、実際には二進数の減算の繰返しなので、
うまく改良できれば効率化できるかも
● ブレントの算法
・ 二進数同士のGCDを高速に行う算法
・ 2で割る(最下位桁の0を取り除く)ことと減算だけを使う
・ gcd(a,b)=gcd(a',b')×2↑e とし、奇数となる gcd(a',b') に着目
第07節 [2] ブレントの算法
・
・
・
・
事前処理として、下位桁の共通の0を取り除く(2↑eで割る)
さらに一方のみの0も取り除く(2は共通因数にならないので無視)
大きい方から小さい方を引く(ニコマコスの算法)
差が0(両者が一致)になれば、直前の値がGCD'になっている
・ 上位桁というより下位桁から減らしていく方法
・ 1回の減算で必ず1桁以上が減るので、log2(a) の計算量となる
・ 負荷の高い除算を使わないので、ビットレベルの実装を工夫すれば、
ユークリッドの互除法よりも高速
164
10101000[2] ⇒ 101010 ⇒
二進数
前処理
00
10101 ⇒ 10101 ⇒ 10101 ⇒ 10010 ⇒ 1001 ⇒ 110 ⇒
移動
移動
減算
移動 一致
4×
二進数
前処理
減算
移動
10000100[2] ⇒ 100001 ⇒ 100001 ⇒ 1100 ⇒
132
減算
11
3 = 12
11 ⇒
11 ⇒
11 ⇒
11 ⇒
一致
11
第00節 [1] ユークリッドの不定方程式
ユークリッドの一次不定方程式 23x-10y=-2 を満たす具体解を1つ求めよ。
整除演算 23÷10=2‥3 より、 23x-10y=10(2x-y)+3x と式変形し、
z=2x-y とおいて変数変換を行い、小さな係数の方程式 10z+3x=-2 に帰着させる。
ユークリッドの互除法のように、 この操作を続け、一方の係数が1となる自明な方程式の
具体解(他方の解は0)を求める。変数変換を逆算しながら、各変数を求めていく。
整除演算 [ 10÷3=3‥1 ] より、 [ 10z+3x=3(3z+x)+z ] と式変形し、
[ w=3z+x ] とおいて変数変換を行い、
小さな係数の方程式 [ 3w+z=-2 ] に帰着させる。
ここで、 zの係数が1となり、自明な具体解 w= [ 0 ], z= [ -2 ] を得る。
変数変換の式を逆算し、 x= [ w-3z ], y= [ 2x-z ] から、
具体解 x= [ 6 ], y= [ 14 ] を得る。
与式を図形の方程式とみると、具体解は、直線 L : 23x-10y=-2 上の
格子点(XY座標がともに整数の点)になっている。
直線の傾きを考えると、xが10増えれば、yは23増えるという関係になっている。
よって、他の具体解として、 x= [ 16 ], y=[ 37 ] や、 x= [ 26 ], y= [ 60 ] が挙げられる。