Matt Bowcock // mbowcock.com

The code below is exercises 1.16 and 1.17. I’ll finish up 1.18 and 1.19 some time in the future. I’ve created a repository on github to store the code I write while working through SICP – if you’re interested it can be found at
http://github.com/mbowcock/SICP.

Exercise 1.16 -

(define (square n)
  (* n n))

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

(define (fast-expt-new b n)
  (fast-expt-iter b n 1))

Exercise 1.17 –

(define (double n)
  (* n 2))

(define (halve n)
  (/ n 2))

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

Had a little time and got it done quicker than I expected. Problem 1.12 was to write a procedure to calculate elements of pascals triangle. I took that to mean calculate the value at position n of a given row. Take a look -

(define (pascal row n)
  (cond ((> n row) 0)
        ((or (= n 1) (= n row)) 1)
        (else (+ (pascal (- row 1) n) (pascal (- row 1) (- n 1))))))

As I said in a post earlier this week I’ve begun reading and working on the problems in SICP. I just read chapter 1 section 2.2 on tree recursion and completed problem 1.11 and plan to do 1.12 and 1.13. Problem 1.11 was creating recursive and iterative procedures to calculate the following function:

The recursive function was straight-forward:

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

Writing the procedure as an iterative process wasn’t as trivial. I initially expected it would be easy and sat down to write the code without really thinking about the problem, but wrapping my head around how to maintain the state needed for 3 function calls didn’t compute. So I resorted to pencil and paper – I wrote out the iterations of the function for n=0 through n=5 and the solution became clear:

(define (f-iter a b c count n)
  (cond ((< n 3) n)
    ((= count n) c)
      (else (f-iter b c (+ c (* 2 b) (* 3 a)) (+ count 1) n))))
     
(define (f2 n)
  (f-iter 0 1 2 2 n))

As a quick comparison of run-time for the 2 procedures I ran them with the same n value (n=30). For f(30) (recursive) the procedure took approximately 16 seconds to finish. For f2(30) (iterative) the procedure finished in less than a second. I tried higher numbers but the recursive process just takes to long – I killed the process at 3 minutes when running it for n=35. I’ve run the iterative process with n up to 150 and it completes in less than 1 second.

Working my way through SICP has a goal I’ve had for a while but never seemed to get to.  However – this past week I started reading the book and working on the exercises and am looking forward to the challenge.  I skipped a couple of exercises in the first section but came up with the following to exercise 1.8:

(define (cube x)
  (* x x x))

(define (abs-val x)
  (cond ((> x 0) x)
    ((= x 0) 0)
    ((< x 0) (- x))))

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

(define (good-enough? guess x)
  (< (abs-val (- (cube guess) x)) 0.001))

(define (cube-root-iter guess x)
  (if (good-enough? guess x)
    guess
    (cube-root-iter (improve guess x) x)))

(define (cube-root x)
  (cube-root-iter 1.0 x))

Along with the exercises in SICP I plan to also apply my new found knowledge to some of the problems from Project Euler.  The solution I came up with for exercise 1 was probably overkill but it worked and should work for larger sets of numbers:

(define (calc-iter total count limit)
  (if (= count limit)
    total
    (calc-iter
        (+ (if (or (= (modulo count 3) 0) (= (modulo count 5) 0)) count 0) total)
        (+ count 1)
        limit)))

(define (calc x)
  (calc-iter 0 0 x))

(calc 1000)