SICP 孤読書会 - 1.2 手続きとその生成するプロセス (1.2.4 〜 1.2.6)

SICP

1.2.4 べき乗

引数として底 b と正の整数の指数 n をとり、 bn を計算する手続きは再帰的な手続き、反復的な手続きで記述することができる。

再帰的な手続きでは、Θ(n)ステップ、Θ(n)スペースを必要とする。
反復的な手続きでは、Θ(n)ステップ、Θ(1)スペースを必要とする。

逐次平方を使うとより少ないステップ数でべき乗の計算をすることができる。

逐次平方では、順番に

(b * (b * (b * (b * (b * (b * (b * b))))))

を計算するのではなく

b^2 = b・b
b^4 = b^2・b^2
b^8 = b^4・b^4

を使って計算を行う。

それにより、Θ(log n)ステップ、Θ(log n)スペースでべき乗の計算をすることができる。


問題 1.16 〜 1.19

SICP/ch1/1-16.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-17.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-18.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-19.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-19.txt at master · snufkon/SICP · GitHub

github に解答をおいておく。


1.2.5 最大公約数

２つの整数a, b の最大公約数(GCD)は、a, b の両方を剰余なしに割り切る最大の整数と定義する。

GCD の計算法として Euclid のアルゴリズムがある。

Euclid のアルゴリズムを手続きとして記述すると

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

となる。

この手続は反復的なプロセスを生成する。

問題 1.20

SICP/ch1/1-20.scm at master · snufkon/SICP · GitHub

github に解答をおいておく。


1.2.6 例： 素数性のテスト

整数 n の素数性を調べるアルゴリズムとして、２つの方法を述べる。

除数の探索

ある数(n)が素数であることは次のようにしてわかる

 n は n 自身がその最小除数である時に限り、素数である。

一般的な方法。これを元に実装するとΘ(√n) のアルゴリズムになる。


Fermat テスト

素数性をテストする際に Fermat の小定理を利用する。

Fermat の小定理

n を素数、a を n より小さい正の整数とすると、a の n 乗は n を法として a と合同である。

分かりづらい。

n を素数、a を 0 < a < n の整数とすると、a^n を n で割った余りは a になる。

っていうこと。

n が素数でない時は、一般に a < n なる殆どの数について上の関係は成り立たない。
--> 言い換えると、非素数でも上の関係がなり立つ場合がある。

これらを元に実装すると、Θ(log n) のアルゴリズムになる。

除数の探索より高速であるが、確率的方法なため注意が必要。
Fermat テストで得られた答えは確率的にしか正しくない。 より正確に言うと、

n が Fermat テストに失敗 --> n は確実に素数ではない
n が Fermat テストに合格 --> n が素数である可能性が非常に高い

となる。テストに合格しても n が素数であることは保証されない。

Fermat テストの実装時に必要となる expmod については

Fermat の小定理 - hattorix0の日記

の説明が分かりやすかったです。


問題 1.21 〜 1.28

SICP/ch1/1-21.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-22.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-23.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-24.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-25.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-26.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-27.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-28.scm at master · snufkon/SICP · GitHub

github に解答をおいておく。

問題 1.23

gauche には runtime 関数がないので

実行時間の計測 - n-oohiraのSICP日記 - sicp

を参考にさせていただき、方法１で実装。


問題 1.24

fermat-test で利用している random が gauche にないため

(use srfi-27)
(random-integer n)

を利用する。

問題 1.28

何をやればいいか、いまいちピンとこなかったので

Bill the Lizard: SICP Exercise 1.28: The Miller-Rabin test

の実装を見てパクリました。


SICP 孤読書会のメインページは こちら