アルゴリズム論特論(塩田)第4回 (6) 今日のまとめと課題1
今日のまとめ
- ユークリッドのアルゴリズム、拡張ユークリッドアルゴリズムの計算量は $\log^2$ オーダーである。
- ユークリッドのアルゴリズムは再帰的にも書けるが、リソースを圧迫するので奨められない。
課題1
- python, java 等を用いて、多倍長整数に対しても実行できるように拡張ユークリッドアルゴリズムをプログラミングし、
次の $(a,b)$ に対し、
$\mbox{gcd}(a,b)$ と、$\mbox{gcd}(a,b) = ax + by$ を満たす整数の組 $(x,y)$ をひとつ求めよ。
- $a = 123456789$, $b=777777777$ ( どちらも 9 桁 )
- $a = 2^{300}$, $b = 3^{200}$ ( python なら a = 2 ** 300 のように書けばよい )
- 提出期限 : 5月31日
- メールにて塩田まで。
- pdf