専門コア情報処理演習（塩田クラス）
（理学部 数理情報科学科い組 対象）
第１１回の教材(４）

---

前へ / 戻る

---

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

• 代表的な公開鍵暗号である 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

□　今日の課題

• 残った時間はサンプルプログラムをいじって楽しんでください。 （たとえば数字を変えて実行してみる、とか。）

---

前へ / 戻る