SICP 1.2 exercises cont. 7

1.17

(define (fast-* a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-* a (halve b))))
        (else (+ a (fast-* a (+ b -1))))))

Comments: Pretty straight forward, the main difficulty was figuring out the order of operations which requires a little bit of thinking.

1.18

(define (fast-*-iter current a b)
  (cond ((= b 0) current)
        ((even? b) (fast-*-iter current (double a) (halve b)))
        (else (fast-*-iter (+ current a) a (+ b -1)))))

(define (fast-*-2 a b)
  (fast-*-iter 0 a b))

Comments: I used the idea of an invariant quantity, namely [current + ab]. Some algebra shows that the only way to make it work is to modify a from iteration to iteration which I did’t realize when I dived into coding it.

1.19

(define (fib n)
  (fib-iter 1 0 0 1 n))

; a <- bq + aq + ap ; b<-bp + aq
; a <- (bp + aq)q + (bq+aq+ap)q + (bq+aq+ap)p
; a <- aq^2 + bq^2 + aq^2 + 2bpq + 2apq + ap^2 
; = b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2)
; q' = q(2p+q), p' = p^2 + q^2
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))      ; compute p'
                   (+ (* 2 p q) (square q))      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Comments: Clearly working out p’ and q’ is the key. Conceptually it’s easy to do this problem without fully understanding it. So I reread the problem to convince myself that I understood it.

3 problems done in one day! Granted these were not too hard, but the past few days I’ve been spending less and less time on SICP. In order to get more done, I’m using HabitRPG. For the first 48 hours at least, I’ve been much more productive than I have been since winter break started. Also worth noting is I’ve been using Workflowy to organize my thoughts, annotations, and schedule. It’s a very nice iterface and so far has been a blast to use.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s