Ex 1.8 – Structure and Interpretation of Computer Programs

; Ex 1.8
(define improve-cube-root
  (lambda (x y)
    (/ (+ (/ x (* y y)) (* 2 y))
       3)))

(define cube-root-iter
  (lambda (guess x )
    (define next-guess ( / ( + (/ x (* guess guess)) (* 2 guess))
                           3))
    (if (good-enough-2? next-guess guess)
        next-guess
        (cube-root-iter next-guess x))))

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

Ex 1.7 – Structure and Interpretation of Computer Programs

; Ex 1.7
(define (good-enough-2? guess prev-guess)
  (< (abs (- guess prev-guess)) 0.0001))

(define sqrt-iter-2
  (lambda (guess x)
    (define next-guess (improve guess x))
    (if (good-enough-2? next-guess guess)
        next-guess
        (sqrt-iter-2 next-guess x))))

Ex 1.6 – Structure and Interpretation of Computer Programs

; Ex 1.6
; The function will run forever, because Scheme is applicative order
; so the argument for the else clause will be evaluated causing the
; to routine to run forever.

Ex 1.13 – Structure and Interpretation of Computer Programs

Exercise 1.13 – SICP

We already know that

(1)

We also know that

where

From the hint where

So

So according to the finonacci definition (1)

Using wolfram alpha we can compute

If you plugin the values in the wolfram alpha , you can see that that both expansions at are also the same

Edit hmmm, looks like I missed the point of the problem. The real problem was to prove that Fib(n) approx= phi^n / 2 where phi = (1+sqrt(5))/2. I think I’ll have to redo this proof.

Excercise 1.11 Structure and Interpretation of Computer Programs (SICP)

I’m going through the “Structure and Interpretation of Computer Programs” as a way of compensating for my lack of geek cred.
I was having some problem with wrapping my head around the iterative solution of this exercise (hey it was after a long day at work), so I cheated a bit and looked it up on the internet and found a solution here. So in order to come up with my own solution, I decided to implement a solution using the collector function  or continuation technique for recursion shown or taught in the “Little Schemer” in chapter 8. Below is what I came up with

; Ex 1.11
; recursive solution
(define f-r
  (lambda (n)
    (cond ((< n 3) n)
          (else ( + (f-r (- n 1))
                    (* 2 (f-r (- n 2)))
                    (* 3 (f-r (- n 3))))))))

; Iterative Solution
(define f&co
  (lambda (n col)
    (cond ((< n 3) (col n 1 0))
          ( else (f&co (- n 1)
                       (lambda (a b c)
                         (col (+ a (* 2 b) (* 3 c))
                              a
                              b)))))))

(define f-i
  (lambda (n)
    (f&co n (lambda (a b c) a))))
(display “Recursive Solution”)
(newline)
(map f-r ‘(0 1 2 3 4 5 6))
(display “Iterative Solution using collector function”)
(newline)
(map f-i ‘(0 1 2 3 4 5 6))
                                

Moving from Scheme to OCAML

So I started learning OCAML and I’m already missing Scheme …