香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第1-2章 最大公約数とユークリッドの互除法 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp.

Slides:



Advertisements
Similar presentations
1 高速フーリエ変換 (fast Fourier transform). 2 高速フーリエ変換とは? – 簡単に言うとフーリエ変換を効率よく計算 する方法 – アルゴリズムの設計技法は分割統治法に基 づいている 今回の目的は? – 多項式の積を求める問題を取り上げ、高速 フーリエ変換のアルゴリズムを用いた解法.
Advertisements

©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
0章 数学基礎.
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
香川大学工学部 富永浩之 情報数学1 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之
香川大学工学部 富永浩之 情報数学1 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第4回 配列(2) 情報・知能工学系 山本一公
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
香川大学工学部 富永浩之 情報数学1 第1-2章 最大公約数とユークリッドの互除法 香川大学工学部 富永浩之
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
1. アルゴリズムと計算量.
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
6学年 算数 ~ 式 と 計 算 ~.
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
香川大学工学部 富永浩之 情報数学1 第3-1章 多進法の原理と変換算法 香川大学工学部 富永浩之
香川大学工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学工学部 富永浩之
香川大学工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学工学部 富永浩之
データ構造と アルゴリズム 知能情報学部 新田直也.
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
10. 積分 積分・・確率モデルと動学モデルで使われる この章は計算方法の紹介 積分の定義から
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
離散数学I 第6回 茨城大学工学部 佐々木稔.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
第7回 条件による繰り返し.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
4. 組み合わせ回路の構成法 五島 正裕.
情報処理3 第5回目講義         担当 鶴貝 達政 11/8/2018.
アルゴリズムとチューリングマシン 「もの」(商品)としてのコンピュータ 「こと」(思想)としてのコンピュータ アルゴリズム
岩村雅一 知能情報工学演習I 第11回(後半第5回) 岩村雅一
ディジタル回路 3. 組み合わせ回路 五島 正裕 2018/11/28.
第7回 条件による繰り返し.
情報セキュリティ  第8回 RSA暗号.
トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
5.RSA暗号 素因数分解の困難性を利用した暗号.
25. Randomized Algorithms
Q q 情報セキュリティ 第6回:2007年5月25日(金) q q.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
11.再帰と繰り返しの回数.
4. システムの安定性.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
香川大学創造工学部 富永浩之 情報数学1 第1-3章 素数と素因数分解 香川大学創造工学部 富永浩之
香川大学創造工学部 富永浩之 情報数学1 第1-2章 最大公約数とユークリッドの互除法 香川大学創造工学部 富永浩之
補講:アルゴリズムと漸近的評価.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
行列式 方程式の解 Cramerの公式 余因数展開.
Q q 情報セキュリティ 第5回:2006年5月19日(金) q q.
PROGRAMMING IN HASKELL
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
香川大学創造工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学創造工学部 富永浩之
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
PROGRAMMING IN HASKELL
Q q 情報セキュリティ 第6回:2005年5月26日(金) q q.
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
Cプログラミング演習 ニュートン法による方程式の求解.
プログラミング演習I 数値計算における計算精度と誤差
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
香川大学創造工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学創造工学部 富永浩之
参考:大きい要素の処理.
高度プログラミング演習 (07).
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
香川大学創造工学部 富永浩之 情報数学1 第3-3章 多進法での四則演算 香川大学創造工学部 富永浩之
知能情報工学演習I 第10回( C言語第4回) 課題の回答
Presentation transcript:

香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第1-2章 最大公約数とユークリッドの互除法 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 最大公約数の性質 ■ ユークリッドの互除法の漸化式と計算過程 ■ 互除法の剰余列とアルゴリズム 概 要 ■ 最大公約数の性質 整除関係 互いに素 公約数 公倍数 GCD LCM ■ ユークリッドの互除法の漸化式と計算過程 gcd(a,b) 初期条件 漸化式 ■ 互除法の剰余列とアルゴリズム 剰余列 機械性と停止性 手続と算法 ■ 互除法の効率性と最小剰余による改良 最小剰余 ■ 互除法の図形的意味とブレントの算法 二コマコスの算法 ブレントの算法

第01節 [1] 公約数と公倍数 6の約数 ±1, ±2, ±3, ±6 1は全ての約数 6の約数 ±1, ±2, ±3, ±6 1は全ての約数 6の倍数 0, ±6, ±12, ±18, ‥ 0は全ての倍数 12と18の公約数 1, 2, 3, 6 10と15の公倍数 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の倍数 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> gcd(a,b) = gcd(b,a) 交換律 <2> gcd(-a,b) = gcd(a,b) 符号無視 <3> gcd(a,1) = 1 1は全ての約数 <4> gcd(a,0) = a 0は全ての倍数 (a>0) <5> gcd(ka,kb) = k×gcd(a,b) 共通因数の括出し (k>0) <5>’ gcd(ab,b) = b 整除関係 (b>0) <6> gcd(a,b) = gcd(a-b,b) 差への還元 <6>’ gcd(a,b) = gcd(a%b,b) 剰余への還元 (b≠0) <5> gcd(42,30)=gcd(6×7,6×5)=6×gcd(7,5)=6×1=6 <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 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> a⊥b のとき lcm(a,b) = a×b <2> 余因数の括出し lcm(a,b) = a’×b’×gcd(a,b) <3> 共通因数の括出し lcm(ka,kb) = k×lcm(a,b) <4> 積の公式 a×b = gcd(a,b)×lcm(a,b) ・ LCMは、2数の積をGCDで割って求めることができる ・ 実際の計算では、オーバーフローを防ぐため、 一方をGCDで割ってから、他方を掛ける ・ 正整数の組 a,b に対し、GCDとLCMの値が分かれば、 一方 a から他方 b が一意に求められる

第04節 [1] ユークリッドの互除法の定義 gcd(a,b) = { a ; b=0 { gcd(b,a%b) ; else 古代ギリシャの数学者ユークリッドが発見(?) 世界最古の算法(アルゴリズム) ‥機械的な計算手順 gcd(a,b) = { a ; b=0 { gcd(b,a%b) ; 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 gcd(17,7)=gcd(7,3)=gcd(3,1)=1 8×6の長方形を覆う、 最大の正方形のタイルは 2×2 ⇒ GCD 3×2のタイルを並べて、 覆える最小の正方形は 6×6 ⇒ LCM 長方形から最大サイズ (短辺)の正方形を 取れるだけ除く ⇒ <6>’ 縦横を置き換えて、 同様に繰り返す ⇒ <4> 残余がなくなれば、 そのサイズがGCD ⇒ <1> gcd(17,7)=gcd(7,3)=gcd(3,1)=1

第04節 [2] ユークリッドの互除法の計算過程 k a b q r 0 48 ÷ 34 = 1 ‥ 14 gcd(48,34) ------------------------------ 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 と入替え 回 1 2 3 4 5 20 11 9 12 8 13 7 6 14 15 16 17 18 19 10

第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 剰余条件より 狭義単調減少 N(1)>N(2)>‥>N(p)>N(p+1)=0 GCDの性質より gcd(a,b)=gcd( N(k), N(k+1) )=N(p) while ( b != 0 ) { t = b; b = a%b; a = 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 4回 13 ÷ 8 = 1 ‥ +5 最小 13, 8, 3, 1, 0 2回 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 ⇒ 10101 ⇒ 10101 ⇒ 10101 ⇒ 10010 ⇒ 1001 ⇒ 110 ⇒ 11 二進数 前処理 移動 減算 移動 減算 移動 一致 00 4× 3 = 12 二進数 前処理 減算 移動 一致 10000100[2] ⇒ 100001 ⇒ 100001 ⇒ 1100 ⇒ 11 ⇒ 11 ⇒ 11 ⇒ 11 ⇒ 11 132

第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 ] が挙げられる。