問題 1.16

SICP

無職の間にSICPも読んでみる。目標は焦らずしっかりと読む。問題の解答をさらす。解く順番は出来るだけリニア。

問題 1.16
fast-exp のように、逐次平方を使い、対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ。（ヒント： (bn/2)2 = (b2)n/2 に注意し、指数 n と底 b の他にもう一つの状態変数 a を用意する。状態の移変りで積 a * bn が不変であるように状態遷移を定義する。プロセス開始時に a を 1 とし、プロセス終了時に a が結果になるようにする。一般に、状態の移変りに不変のままの不変量 (invariant quantity) を定義する技法は、反復的アルゴリズムの設計に有用である。）


Exercise 1.16
Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (bn/2)2 = (b2)n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a * bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)


かなり試行錯誤した。


まずは、再帰 O(n) の手続き。

(define (expt base n)
  (if (= n 0)
      1
      (* base (expt base (- n 1)))))


そして、反復 O(n) の手続き。

(define (expt base n)
  (define (expt-iter x counter)
    (if (> counter n)
        x
        (expt-iter (* base x) (+ counter 1))))
  (expt-iter 1 1))


ほいでもって、再帰 O(log n) の手続き。

(define (square x)
  (* x x))
(define (even? n)
  (= (remainder n 2) 0))
(define (expt base n)
  (cond ((= n 0) 1)
        ((even? n) (square (expt base (/ n 2))))
        (else      (* base (expt base (- n 1))))))


これが、問題の解答。反復 O(log n) の手続き。
n が偶数の時と奇数の時で、ネストされている反復プロセスの引数の更新の仕方を変える。

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


試行錯誤のうえ、最初に考えたやりかた。O(log n) と O(n) のハイブリッド（？）
n の 最寄の 2 の乗数まで O(log n) で求めて、そこから線形反復に切り替わる。 n が 2 の乗数だと O(log n) で動作するので、それなりに早いけど、　n が 2 の乗数 -1 だと遅い。

(define (expt base n)
  (define (le a b) (or (< a b) (= a b)))
  (define (expt-iter a counter)
    (cond ((>  counter       n) a)
          ((le (* counter 2) n) (expt-iter (* a a base) (* counter 2)))
          (else                 (expt-iter (* a   base) (+ counter 1)))))
  (expt-iter 1 1))


下記のコードで、実行時間を計測してみる。

(define (hoge n) (dotimes (i n) (pow 2 1024)))
(define (hoge n) (dotimes (i n) (pow 2 1023)))


(hoge 5000) の結果

n 再帰 O(n) 反復 O(n) 再帰 O(log n) 反復 O(log n) 反復 O(log n)+O(n)
1024 22.870 15.730 0.410 0.350 0.340
1023 19.610 13.660 0.630 0.460 10.580


やっぱり、最後のパターンは 1024 (210) だと早いが、 1023 (210-1) だと遅い。


ごちょごちょやって、どうにか出来たけど、きっちり理解できていないので、もうちょっと考え方をまとめないといけない。


つづき：　id:mohayonao:20090317:1237302159