SICPゼミ第3回

練習問題1.17

対数時間で掛け算を定義せよ(再帰的に)

(define (fast-prod b n)
  (define (even? a)
    (= (remainder a 2) 0))
  (define (double a) (* 2 a))
  (define (halve a) (/ a 2))
  (cond ((= n 0) 0)
        ((even? n) (double (fast-prod b (halve n))))
        (else (+ b (fast-prod b (- n 1))))))

練習問題1.18

1.16,1.17を参考に掛け算を反復プロセスで定義

(define (fast-prod b n)
  (define (double a) (* 2 a))
  (define (fast-prod-iter count prod)
    (cond ((= 0 n) 0)
          ((= n count) prod)
          ((<= (double count) n) (fast-prod-iter (double count) (double prod)))
          (else (fast-prod-iter (+ count 1) (+ prod b)))))
  (fast-prod-iter 1 b))

イテレータ上から回さないと対数時間にならなくねと言われたので書き直し

(define (fast-prod b n)
  (define (double a) (* 2 a))
  (define (halve a) (/ a 2))
  (define (even? a) (= (remainder a 2) 0))
  (define (fast-prod-iter count prod)
    (cond ((= count 0) prod)
          ((even? count) (fast-prod-iter (halve count) (double prod)))
          (else (fast-prod-iter (- count 1) (+ prod b)))))
  (fast-prod-iter n 0))

練習問題1.19

(define (square n) (* n n))
(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        (( even? count)
         (fib-iter a
                   b
                   (+
                    (square p)
                    (square q))
                   (+
                    (* 2 p q)
                    (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))