Solution to SICP Exercise 1.19

Structure and Interpretation of Computer Programs

Solution to Exercise 1.19:

Tqp is defined as:

abq + aq + ap
bbp + aq

If we apply Tpq to itself, we get T2pq:

a ← (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
b ← (bp + aq)p + (bq + aq + ap)q

With some manipulation, this can be rewritten as:

ab(2pq + q2) + a(2pq + q2) + a(p2 + q2)
bb(p2 + q2) + a(2pq + q2)

As we are looking for a transformation of the form

abq′ + aq′ + ap
bbp′ + aq

It should be fairly obvious that

p′ = p2 + q2
q′ = 2pq + q2

Now we can modify our program:
(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
(sum-of-squares p 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))
(- count 1)))))

(define (square x)
(* x x))

(define (sum-of-squares x y)
(+ (square x) (square y)))

Solution to SICP Exercise 1.18

Structure and Interpretation of Computer Programs

Solution to Exercise 1.18:

(define (double x)
(+ x x))

(define (halve x)
(/ x 2))

(define (even? n)
(= (remainder n 2) 0))

(define (it-fast-mult a b)
(iter 0 a b))

(define (iter total a b)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) (+ total a))
((even? b) (iter total (double a) (halve b)))
(else (iter (+ total a) a (- b 1)))))

Solution to SICP Exercise 1.15

Structure and Interpretation of Computer Programs

Solution to Exercise 1.15:

Part a. Here’s the process of (sine 12.15).

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))

There are clearly 5 applications of the p procedure.

Part b. We can see from the process above that the p procedure is applied for every power of 3.0 in angle. The order of growth in the number of steps is therefore Θ(log3n). Because the p procedures accumulate for every power of three, the growth of process in space is also Θ(log3n).

SICP, Dijkstra, and Plato! Oh my!

As somebody reading and working through the exercises in SICP, I enjoyed the paper Jim Brown posted about it entitled What’s in the box?: Abstraction and Regimes of Truth in Computer Programming. While the focus of the article is on what it means to treat procedures a black boxes, the part I found most interesting is where he likens the differences between the bottom-up approach of SICP and the top-down approach of Dijkstra to the differences between Aristotle’s and Plato’s epistemologies:

For Plato, we must understand truth prior to entering into dispute or argument, otherwise we will find ourselves lured by faulty “resemblances”. This is Dijkstra’s point when he warns of the dangers of testing programs before they are properly finished. One should know their program perfectly before testing it. Trial and error was a flawed technique for these programmers. Abelson and Sussman, on the other hand, are more interested in the negotiation and collaboration that happens in the programming community. In this sense, their method seems more akin to Aristotle’s description of rhetoric. In Book I of the Rhetoric, he differs from Plato’s view of rhetoric as mere persuasion: “[Rhetoric’s] function is not simply to succeed in persuading, but rather to discover the means of coming as near such success as the circumstances of each particular case allow (1328). Rhetoric is then useful because it gets us as close to truth as possible, and this should remind us of Abelson and Sussman’s assertion that, “we become convinced of program truth through argument.”

Solution to SICP Exercise 1.14

Structure and Interpretation of Computer Programs

Solution to Exercise 1.14:

The process generated by the count-change procedure
Click to enlarge.

The count-change is Θ(n) in space. Like the fib procedure, the space required is equal to the maximum depth of the tree, which occurs on the combination that is all pennies.

I believe, though I could very well be wrong, that the process is Θ(n2) in time as the calls to cc tend to double with increments to n.

I couldn’t get conclusive timing numbers out of DrScheme to confirm this belief. Here’s the code I was using to test

(require (lib "" "srfi"))
(map (lambda (amount)
(let ((start-time (current-time time-process))
(change (count-change amount))
(end-time (current-time time-process)))
(let ((diff (time-difference end-time start-time)))
(list (time-second diff) (time-nanosecond diff)))))
(list 100 200 300 400))

The output was ((0 160000) (0 2810000) (0 1560000) (1 6560000)). I don’t understand why the third time was consistently less than the second. Anybody care to enlighten me?