平成１５年度 専門コア情報処理演習 _y
（理学部 数理情報科学科イ組 対象、塩田教官） _y
１月１９日の教材（４）

---

前へ / 戻る

---

□　計算量理論体験その１：べき乗計算

• 代表的な公開鍵暗号である RSA 暗号では、
  　　a^e mod n
  というべき乗計算が、10進150桁程度の a, e, n に対して行われます。 test5.p はそのサンプルプログラムです。

• コンパイルして実行してみましょう。

  gcc　-o　t5　test5.c　;　t5

• 実行時間が表示されますが、 単純に１回１回掛けて行くと10進8桁程度でもこれだけの時間が掛かってしまうのに対し、 反復２乗法というテクニックを用いると瞬時に計算が終わっていることに注目してください。

□　計算量理論体験その２：素数判定

• test6.c は素数判定のサンプルプログラムです。

• 定義を正直に読むと、自然数 n は、2 以上 n 未満の数で割り切れないとき、素数である訳ですが、
  • n が奇数なら、偶数で割ってみる必要はない
  • n の平方根より大きい数で割ってみる必要はない
    （n の平方根より大きい約数があれば、商は平方根より小さい約数になるので）

  ということを考慮すると計算は飛躍的に早くできます。

• コンパイルして実行してみましょう。

  gcc　-o　t6　test6.c　-lm　;　t6

□　誤差論体験：逆数の和

• test7.c は自然数の逆数の和を計算するサンプルプログラムです。

• 計算機上では「実数」と言っても有限桁の計算しかできないために、 「桁落ち」や「積み残し（情報落ち）」と呼ばれる現象が起こって誤差を生ずることがあります。

• 自然数の逆数を 1 から順に足してゆくと、和に対して足される数が極端に小さくなってゆくために 「積み残し」が起こり誤差が大きくなります。

• 逆に大きい和の逆数から足してゆくと「積み残し」が起こりにくいので誤差が小さくなります。

• コンパイルして実行してみましょう。

  gcc　-o　t7　test7.c　;　t7

□　今日は課題はありません

• 残った時間はサンプルプログラムをいじって楽しんでください。

---

前へ / 戻る