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回で計算出来てしまう。
凄いね。これを、「増加の程度が対数的である」と言うらしい。
問題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乗しろってことね。ナルホド。反復苦手・・・。