Peter Sheats’ Blog

So I never really expected this course to be so much about math – but I am beginning to see the importance of math more and more. It makes me wish that I had focussed more on math in school. Anyway, here’s my solution after some great help from our SICP study group.

Here’s what we are given:

a = bq + aq + ap
b = bp + aq

And we are told to apply the transformation Tpq to (a, b) using the definitions above. So we actually have:

(bq + aq + ap, bp + aq) and if we were going to apply the transformation again we would need to substitute for a and b in that pair by using algebra.

So the first part of that pair would be:

a = (bp + aq)q + (bq+aq + ap)q + (bq +aq + ap)p – by replacing every a and b with the definitions above
a = bpq + aq² + bq² + aq² + apq + bpq + aqp + ap² — factor in the q’s and p’s
a = 2bpq + 2aq² + 2aqp + bq² + ap² – group similar terms
a = b(2pq + q²) + a(2pq + q²) + a(p² + q²) — factor out a’s and b’s

b = (bp + aq)p + (bq + aq + ap)q — replacing
b = bp² + apq + bq² + aq² + apq — multiply out
b = 2apq + aq² + bp² + bq² — group similar terms
b = a(2pq + q²) + b(p² + q²) — factor out a and b

So we are looking to do the following transformations:
a = bq’ + aq’ + ap’
b = bp’ + aq’

So by our calculations above we can see that
p’ = p² + q²
q’ = 2pq + q²

So then substituting those values into our procedure:

(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
                   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)))))

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

Here are the rules for the Russian peasant method:

• Write each number at the head of a column.
• Double the number in the first column, and halve the number in the second column.
  If the number in the second column is odd, divide it by two and drop the remainder.
• If the number in the second column is even, cross out that entire row.
• Keep doubling, halving, and crossing out until the number in the second column is 1.
• Add up the remaining numbers in the first column. The total is the product of your original numbers.

So my procedure will keep track of a, b, and sum. On each iteration the sum will be set to a + sum only when b is odd. When b = 1 the answer will be a + sum.

; We don't care about the remainder of 1
; so we only want to divide the next even number
(define (halve x)
  (if (even? x)
      (/ x 2)
      (halve (-  x 1))))

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

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

(define (mul-help a b sum)
  (if (= b 1)
      (+ a sum)
      (mul-help (double a)
                (halve b)
                (if (even? b)
                    sum
                    (+ a sum)))))

(define (mul a b)
  (mul-help a b 0))

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

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

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

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

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

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

(define (exp b n)
  (exp-iter b n 1))

(define (exp-iter b n a)
  (cond ((= n 1) a)
        ((even? n)(exp-iter (square b)
                            (/ n 2)
                            (square b)))
        (else (* b (exp-iter b (- n 1) a)))))

a. The procedure p is applied 5 times.

(sine 12.15))

(p (sine 4.05)))

(p (p (sine 1.35))))

(p (p (p (sine .45)))))

(p (p (p (p (sine .15))))))

(p (p (p (p (p (sine .05)))))))

b. So I’m really unclear about a lot of this but I will try to express what I can based on my research and what other people answered. It appears that the order of growth in space and number of steps are related to the division of the angle by 3. I am learning then that this means that it is logarithmic. A logarithmic unit is and abstraction technique used in mathematics to express any quantity that is proportional to the value of a logarithm function. A logarithm function is written like this: log_b(x). It is used to represent y = log_b(x) and is equivalent to x = b^y. So we are expressing that something (b but the b or base is usually irrelevant according to footnote 37 on pate 46 in SICP) is proportionate to some power (y) is equal to x.

So in our case, we are dividing a by 3 until we arrive to something less than 0.1. How many times we have to do that is what determines the number of steps our procedure has to take. So we would express that as θlog₃(a) to say that the number or steps required is whatever it takes to multiply θ * 3 * 3 . . . * 3 to equal our angle, a. I guess in our case θ would be .1. And since the base of 3 is irrelevant our final answer is θlog(a). The 3 is irrelevant because we are really just expressing the idea of something being proportionate to something else.

Anyway, if you’re reading this try not to laugh too much :) My last math class was Calculus in my freshman year of college which was 7 years ago. And as I recall, I wasn’t too interested in math or programming at the time. Now I am seeing the importance of math and wish I could go back.

Please feel free to comment and correct my thinking.

The number of steps or space required is directly proportional to n since there is always the case of n pennies. So Θ(n).  The time would be exponentially related to n since you have to compute every single possible case.

Ok, so I’m not taking this class to learn about math proofs so instead I wrote a program to test out the equations:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(define (o) (/ (+ 1 (sqrt 5))
              2))

(define (u) (/ (- 1 (sqrt 5))
              2))

(define (proof n)
  (/ (- (exp (o) n)
        (exp (u) n))
     (sqrt 5)))

(define (exp x e)
  (exp-iter x e 1 1))

(define (exp-iter x e count product)
  (if (< e count)
      product
      (exp-iter x e (+ 1 count) (* product x))))

(define (sqrt x)
  (sqrt-iter 1.0 0.0 x))

(define (sqrt-iter guess last-guess x)
  (if (good-enough? last-guess guess)
      guess
      (sqrt-iter (improve guess x)
                 guess
                 x)))

(define (good-enough? guess last-guess)
  (< (abs (- guess last-guess)) 0.001))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (abs x)
  (if (< x 0)
      (- x)
      x))

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

Test:

> (fib 10)
55
> (proof 10)
55.000000000027384
>

(define (p y x)
  (cond ((= y x) 1)
        ((= y 1) 1)
        ((= x 1) 1)
        (else
         (+ (p (- y 1) (- x 1))
            (p (- y 1) x)))))

(define (pascal y)
  (pic y 1))

(define (pic y count)
  (cond ((< y count) (newline))
        (else (print-row count 1)
              (pic y (+ 1 count)))))

(define (print-row y x)
  (cond ((> x y) (newline))              ; last number in row
        (else  (write (p y x))
               (print-row y (+ x 1)))))
 

; f(n) = n if n < 3
; f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3

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

; iterative
(define (i n)
  (if (< n 3)
      n
      (iter 2 1 0 3 n)))

(define (iter a b c count n)
  (define new-a (+ a (* 2 b) (* 3 c)))
  (if (= count n)
      new-a
      (iter new-a
            a
            b
            (+ count 1)
            n)))

(A 1 10)(A (0 (A 1 9)))

(A 0 (A 0 (A 1 8)))

(A 0 (A 0 (A 0 (A 1 7))))

(A 0 (A 0 (A 0 (A 0 (A 1 6)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))

(A 0 (A 0 (A 0 (A 0 (A 0 32)))))

(A 0 (A 0 (A 0 (A 0 64))))

(A 0 (A 0 (A 0 128)))

(A 0 (A 0 256))

(A 0 512)

1024(A 2 4)(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

(A 1 (A 0 (A 0 (A 1 2)

Um, I think this is going to go for a long time so since the instructions don’t say to do it by hand the answer is 65,536.

And (A 3 3) is the same 65,536.

(define (f n) (A 0 n)) = 2n

(define (g n) (A 1 n)) = 2ⁿ

(define (h n) (A 2 n)) = I dunno