アルゴリズム論特論(塩田)第4回 (6) 今日のまとめと課題1

今日のまとめ

  • ユークリッドのアルゴリズム、拡張ユークリッドアルゴリズムの計算量は $\log^2$ オーダーである。
  • ユークリッドのアルゴリズムは再帰的にも書けるが、リソースを圧迫するので奨められない。

課題1

  • python, java 等を用いて、多倍長整数に対しても実行できるように拡張ユークリッドアルゴリズムをプログラミングし、 次の $(a,b)$ に対し、 $\mbox{gcd}(a,b)$ と、$\mbox{gcd}(a,b) = ax + by$ を満たす整数の組 $(x,y)$ をひとつ求めよ。
    1. $a = 123456789$, $b=234567891$ ( どちらも 9 桁 )
    2. $a = 2^{317}$, $b = 3^{200}$
      ( python なら
         a = 2 ** 317
      のように書けばよい。java なら
         BigInteger a = (new BigInteger("2")).pow(317);
         BigInteger a = (BigInteger.valueOf(2)).pow(317);
      のように書く。)
  • 提出期限 : 5月27日
  • メールにて塩田まで。
  • pdf