SICP 1.2 exercises cont. 7Posted: January 13, 2013
(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.
(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.
(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.