SICPを読む(13) 1.2.4 & 問題1.16 対数的はスゲー

SICPスゲーおもろい。

今までは指数的増加を扱っていましたが、対数的に低減させていくというのが今回のテーマ。

対数的ってワカリズライけど、1000回の計算が10回で出来たら凄いよね!!

というお話し。

べき乗

nのn乗を計算するとき、

b^0 = 1
b^n = b * b^n-1

と、再帰的に定義出来るが、計算回数はnに比例する。

しかし、重複部分が多いので、

b^2 = b * b
b^4 = b^2 * b^2
b^8 = b^4 * b^4

と、偶数のべき乗の時、重複部分を一緒に計算すれば良い。

2の10乗を計算すると

2^10
(2^5 * 2^5)
(2^5)^2
2 * (2^4)^2
2 * (2^2 * 2^2)^2
2 * ((2^2)^2)^2

こんな感じ。

2の10乗の計算回数を5回まで減らすことが出来ました。1000乗でも、14回で計算出来てしまう。

凄いね。これを、「増加の程度が対数的である」と言うらしい。

対数の威力

対数の威力を、gnuplotで確認してみます。

gnuplot> plot log(x)

段々、傾きが緩くなっていきます。

対数的ってすげぇ。

問題1.16

意味不明な技を使ってしまった・・・恥ずかしいけど晒しておこう。

(define (expt b n)
 (define (iter product counter)
  (cond ((= counter 0) product)
        ((even? counter) (iter (* product (expt b (/ counter 2))) (/ counter 2)))
        (else (iter (* b product) (- counter 1)))))
 (iter 1 n))

計算回数は、変化なしです・・・いや、増えてる・・・。

解答を見て修正。

(define (expt b n)
 (define (iter b product counter)
  (cond ((= counter 0) product)
        ((even? counter) (iter (* b b) product (/ counter 2)))
        (else (iter b (* b product) (- counter 1)))))
 (iter b 1 n))

基数を2乗しろってことね。ナルホド。反復苦手・・・。