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

情報数学１第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)
第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)を求める。変数変換を逆算しながら、各変数を求めていく。
整除演算 [
] より、 [
] と式変形し、
[
] とおいて変数変換を行い、小さな係数の方程式 [
] に帰着させる。
ここで、 zの係数が1となり、自明な具体解 w＝ [
], z＝ [ ] を得る。
変数変換の式を逆算し、 x= [
], y＝2x－z から、
具体解 x＝ [ ], y＝ [ ] を得る。
与式を図形の方程式とみると、具体解は、直線 L : 23x－10y＝-2 上の
格子点(XY座標がともに整数の点)になっている。
直線の傾きを考えると、xが10増えれば、yは23増えるという関係になっている。
よって、他の具体解として、 x＝ [ ], y＝[
] や、 x＝ [ ], y＝ [ ] が挙げられる。

Download Report