# weima learns to program

my attempt to do the exercises in sicp.

## Monday, June 30, 2008

### sicp exercise 1.37

;  Exercise 1.37. a. An infinite continued fraction is an expression of the form
;
;
;
;  As an example, one can show that the infinite continued fraction expansion with the Ni and the Di
;  all equal to 1 produces 1/phi , where phi is the golden ratio (described in section 1.2.2). One way
;  to approximate an infinite continued fraction is to truncate the expansion after a given number of
;  terms. Such a truncation -- a so-called k-term finite continued fraction -- has the form
;
;
;  Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the
;  terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k)
;  computes the value of the k-term finite continued fraction. Check your procedure by approximating
;  1/phi using
;
;   (cont-frac (lambda (i) 1.0)
;              (lambda (i) 1.0)
;              k)
;
;  for successive values of k. How large must you make k in order to get an approximation that is accurate
;  to 4 decimal places?
;
;  b. If your cont-frac procedure generates a recursive process, write one that generates an iterative
;  process. If it generates an iterative process, write one that generates a recursive process.

(define (cont-frac-recur n d k)
(define (iter i)
(if (> i k)
0
(/ (n i) (+ (d i) (iter (+ i 1))))))
(iter 1))

(display (cont-frac-recur (lambda(i) 1.0) (lambda(i) 1.0) 100))(newline)

(define (cont-frac-iter n d k)
(define (iter i result)
(if (= i 0)
result
(iter (- i 1) (/ (n i) (+ (d i) result)))))
(iter k 0))

(display (cont-frac-iter (lambda(i) 1.0) (lambda(i) 1.0) 1000))(newline)

### sicp exercise 1.36

;  Exercise 1.36. Modify fixed-point so that it prints the sequence of approximations it generates, using
;  the newline and display primitives shown in exercise 1.22. Then find a solution to x^x = 1000 by finding
;  a fixed point of x --> log(1000)/log(x). (Use Scheme's primitive log procedure, which computes natural
;  logarithms.) Compare the number of steps this takes with and without average damping. (Note that you
;  cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(display (rationalize guess 0.00001))(newline)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))

(define (average x y) (/ (+ x y) 2))
(define (func x) (/ (log 1000) (log x)))
(define (func-avg-damp x) (average x (/ (log 1000) (log x))))

;(fixed-point func 2)(newline)
(fixed-point func-avg-damp 2)(newline)

; Answer:
; 4.55554089709763  in 34 steps without average damping
; 4.55555555555556  in 9 steps with average damping

### sicp exercise 1.35

;  Exercise 1.35. Show that the golden ratio (section 1.2.2) is a fixed point of the transformation
;  x --> 1 + 1/x, and use this fact to compute by means of the fixed-point procedure.

(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))

(define (phi x) (+ 1 (/ 1 x)))

(display (rationalize(fixed-point phi 1) 0.0001)) (newline)

### sicp exercise 1.34

;  Exercise 1.34. Suppose we define the procedure
;  (define (f g)
;  (g 2))
;  Then we have
;  (f square)
;  4
;  (f (lambda (z) (* z (+ z 1))))
;  6
;  What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.

(define (f g) (g 2))

; evaluating (f f)
; (f f)
; (f 2)
; (2 2)
; error

## Sunday, June 29, 2008

### sicp exercise 1.33

;  Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing
;  the notion of a filter on the terms to be combined. That is, combine only those terms derived from
;  values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction
;  takes the same arguments as accumulate, together with an additional predicate of one argument that
;  specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following
;  using filtered-accumulate:
;  a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a
;  prime?  predicate already written)
;  b. the product of all the positive integers less than n that are relatively prime to n (i.e., all
;  positive integers i < n such that GCD(i,n) = 1).

(define true  #t)
(define false #f)

(define (square num) (* num num))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test n)
(define (prime-impl n base)
(= (expmod base n n) base))
(prime-impl n (+ 1 (random (- n 1)))))

(define (prime-test n times)
(cond ((= times 0) true)
((fermat-test n) (prime-test n (- times 1)))
(else false)))

(define (prime? n) (prime-test n 10))

(define (filtered-accumulate-recur combiner filter null-value term a next b)
(if (> a b)
null-value
(if (filter a)
(combiner (term a) (filtered-accumulate-recur combiner filter null-value term (next a) next b))
(filtered-accumulate-recur combiner filter null-value term (next a) next b))))

(define (filtered-accumulate-iter combiner filter null-value term a next b)
(define (iter a result)
(if (> a b)
result
(if (filter a)
(iter (next a) (combiner (term a) result))
(iter (next a) result))))
(iter a null-value))

(define (sum-square-if-prime a b)
(define (next x) (+ x 1))
(filtered-accumulate-iter + prime? 0 square a next b))

(display (sum-square-if-prime 4 10)) (newline)

### sicp exercise 1.32

;  Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a still more
;  general notion called accumulate that combines a collection of terms, using some general accumulation
;  function:
;
;  (accumulate combiner null-value term a next b)
;
;  Accumulate takes as arguments the same term and range specifications as sum and product, together
;  with a combiner procedure (of two arguments) that specifies how the current term is to be combined
;  with the accumulation of the preceding terms and a null-value that specifies what base value to use
;  when the terms run out. Write accumulate and show how sum and product can both be defined as simple
;  calls to accumulate.
;  b. If your accumulate procedure generates a recursive process, write one that generates an
;  iterative process. If it generates an iterative process, write one that generates a recursive process.

(define (accumulate-recur combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a) (accumulate-recur combiner null-value term (next a) next b))))

(define (accumulate-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))

(define (sum term a next b)
(accumulate + 0 term a next b))

(define (product term a next b)
(accumulate * 1 term a next b))

### sicp exercise 1.31

;  Exercise 1.31.
;  a. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured
;  as higher-order procedures.51 Write an analogous procedure called product that returns the product of
;  the values of a function at points over a given range. Show how to define factorial in terms of product.
;  Also use product to compute approximations to pie using the formula
;
;  pi/4 = 2/3.4/3.4/5.6/5.6/7 ....
;
;  b. If your product procedure generates a recursive process, write one that generates an iterative
;  process.  If it generates an iterative process, write one that generates a recursive process.

(define (prod-recur term a next b)
(if (> a b)
1
(* (term a)
(prod-recur term (next a) next b))))

(define (prod-iter term a next b)
(define (prod-iter-impl term a next b res)
(if (> a b)
res
(prod-iter-impl term (next a) next b (* (term a) res))))
(prod-iter-impl term a next b 1))

(define (fact n)
(define (next x) (+ x 1))
(define (term x) x)
(prod-iter term 1 next n))

;(display (fact 500)) (newline)

(define (pi)
(define (next x) (+ x 1))
(define (term x)
(cond ((even? x) (/ x (+ x 1)))
(else (/ (+ x 1) x))))
(* (prod-iter term 2 next 1000) 4))

(display (rationalize (pi) 0.000001)) (newline)

### sicp exercise 1.30

;  Exercise 1.30. The sum procedure above generates a linear recursion. The procedure can be rewritten
;  so that the sum is performed iteratively. Show how to do this by filling in the missing expressions
;  in the following definition:
;  (define (sum term a next b)
;     (define (iter a result)
;         (if <??>
;             <??>
;             (iter <??> <??>)))
;     (iter <??> <??>))

(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))

### sicp exercise 1.29

;  Exercise 1.29. Simpson's Rule is a more accurate method of numerical integration than the method
;  illustrated above. Using Simpson's Rule, the integral of a function f between a and b is approximated
;  as
;
;  h(y[0] + 2y[1] + 4y[2] + 2y[3] + ...... 2y[n-2] + 4y[n-1] + y[n])/3
;
;  where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the
;  accuracy of the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns
;  the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between
;  0 and 1 (with n = 100 and n = 1000), and compare the results to those of the integral procedure
;  shown above.

(define (sum-recur term next a b)
(if ( > a b)
0
(+ (term a)
(sum-recur term next (next a) b))))

(define (sum-iter term next a b)
(define (sum-iter-impl term next a1 b1 result)
(if ( > a1 b1)
result
(sum-iter-impl term next (next a1) b1 (+ (term a1) result))))
(sum-iter-impl term next a b 0))

(define (integrate func a b n)
(define h (/ (- b a) n))
(define (next x) (+ x h))
(define (prefix x)
(cond ((even? (/ (- x a) h)) 4)
(else 2)))
(define (term x) (* (prefix x) (func x)))
(/
(*
(+
(func a)
(func b)
(sum-iter term next (+ a h) (- b h)))
h)
3))

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

(display (integrate cube 0 1  100))(newline)
(display (integrate cube 0 1 1000))(newline)

### sicp exercise 1.27

;  Exercise 1.27. Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat
;  test. That is, write a procedure that takes an integer n and tests whether a^n is congruent to
;  a modulo n for every a<n, and try your procedure on the given Carmichael numbers.

(define (carmichael index)
(cond ((= index 1)  561)
((= index 2) 1105)
((= index 3) 1729)
((= index 4) 2465)
((= index 5) 2821)
((= index 6) 6601)
(else 0)))

(define (square num) (* num num))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))

(define (prime-test n base )
(if (= (expmod base n n) base)(display "prime\n")))

(define (prime-carmichael-test num)
(define (prime-carmichael-test-impl base)
(cond ((= base num) 0)
(else (prime-test num base) (prime-carmichael-test-impl (+ base 1)))))
(prime-carmichael-test-impl 2))

(prime-carmichael-test (carmichael 1))(newline)
(prime-carmichael-test (carmichael 2))(newline)
(prime-carmichael-test (carmichael 3))(newline)
(prime-carmichael-test (carmichael 4))(newline)
(prime-carmichael-test (carmichael 5))(newline)
(prime-carmichael-test (carmichael 6))(newline)

; The Carmichael numbers are not prime numbers, but the Fermat test gives a very high probability of
; them being a prime.

### sicp exercise 1.26

;  Exercise 1.26. Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test
;  seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help.
;  When they examine Louis's code, they find that he has rewritten the expmod procedure to use an
;  explicit multiplication, rather than calling square:
;
;     (define (expmod base exp m)
;        (cond ((= exp 0) 1)
;              ((even? exp)
;                  (remainder (* (expmod base (/ exp 2) m)
;                                (expmod base (/ exp 2) m))
;                    m))
;              (else
;                  (remainder (* base (expmod base (- exp 1) m))
;                    m))))
;
;  ``I don't see what difference that could make,'' says Louis. ``I do.'' says Eva. ``By writing the
;  procedure like that, you have transformed the O(log n) process into a O(n) process.'' Explain.

;  Answer: if the procedure square is used, then the expression (expmod base (/ exp 2) m) needs
;  to be calculated once instead of twice when * is used.

## Saturday, June 28, 2008

### sicp exercise 1.25

;  Exercise 1.25. Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod.
;  After all, she says, since we already know how to compute exponentials, we could have simply written
;
;     (define (expmod base exp m)
;         (remainder (fast-expt base exp) m))
;
;  Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

; Answer: She is ofcourse wrong. We are not calculating exponentials, we want to calculate the mod
; of a^n by reducing it in terms of mod of a^(n/2).

; Here i want to present my derivation for the procedure expmod

;----------------------------------------------------------------
;
;   Question: find a^n mod m
;
;   Answer:
;          let us begin by finding x*y mod n
;          reduce x*y mod n in simpler terms
;          assume x,y > n , we can write x and y as follows
;          x = Xn + a,   where a < n
;          y = Yn + b,   where b < n
;
;          then x*y = XY*n^2 + (aY + bX)n + ab
;
;          then,
;
;          x*y mod n is equiv to  a*b mod n because other terms have a n factor
;
;          if y=x then,
;
;          x^2 mod n is equiv to  a^2 mod n
;
;          similarily,
;
;          x^m mod n is equiv to  a^m mod n is equiv to  ((a^m/2 mod n)^2  mod n)
;
;   (define (square num) (* num num))
;
;   (define (expmod base exp m)
;       (cond ((= exp 0) 1)
;             ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
;             (else (remainder (* base (expmod base (- exp 1) m)) m))))
;
;   (display (expmod 6 7 7))(newline)
;
;----------------------------------------------------------------

### sicp exercise 1.24

;  Exercise 1.24. Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat
;  method), and test each of the 12 primes you found in that exercise. Since the Fermat test has O(log n)
;  growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed
;  to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

(define (runtime) (gettimeofday))
(define (difftime start end)
(+
(*
(- (car end) (car start))
100000)
(- (cdr end) (cdr start))))

(define (square num) (* num num))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))

(define (prime? n)
(define (prime-impl n base)
(= (expmod base n n) base))
(prime-impl n (random (- n 1))))

(define (timed-prime-test n)
(start-prime-test n (runtime)))

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (difftime start-time (runtime)))
#f))

(define (report-prime n elapsed-time)
(display n)
(display " *** ")
(display elapsed-time)
(newline)
#t)

(define (search-for-primes start end max)
(define (search-for-primes-impl start count)
(cond ((> start end) 0)
((= count max) 0)
(else (if (timed-prime-test start)
(search-for-primes-impl (+ start 1) (+ count 1))
(search-for-primes-impl (+ start 1) count)))))
(search-for-primes-impl start 0))

(search-for-primes   1000   10000 3)
(search-for-primes  10000  100000 3)
(search-for-primes 100000 1000000 3)

; the time taken to find the 12 primes is lower than the time taken in problems 1.23 and 1.22.
; But i dont find any discrepency, as asked in this problem :(

### sicp exercise 1.23

;  Exercise 1.23. The smallest-divisor procedure shown at the start of this section does lots of needless
;  testing: After it checks to see if the number is divisible by 2 there is no point in checking to see
;  if it is divisible by any larger even numbers. This suggests that the values used for test-divisor
;  should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a
;  procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2.
;  Modify the smallest divisor procedure to use (next test-divisor) instead of (+ test-divisor 1).
;  With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of
;  the 12 primes found in exercise 1.22. Since this modification halves the number of test steps,
;  you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the
;  observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is
;  different from 2?

(define (runtime) (gettimeofday))
(define (difftime start end) (+ (* (- (car end) (car start)) 100000) (- (cdr end) (cdr start))))

(define (smallest-divisor n)
(define (square number) (* number number))
(define (next num)(if (even? num) (+ num 1) (+ num 2)))
(define (divides? n divisor) (= (remainder n divisor) 0))
(define (find-divisor n divisor)
(cond ((> (square divisor) n) n)
((divides? n divisor) divisor)
(else (find-divisor n (next divisor)))))
(find-divisor n 2))

(define (prime? n) (= (smallest-divisor n) n))

(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (difftime start-time (runtime)))
#f))
(define (report-prime n elapsed-time)
(display n)
(display " *** ")
(display elapsed-time)
(newline)
#t)

;(timed-prime-test 3)

(define (search-for-primes start end max)
(define (search-for-primes-impl start count)
(cond ((> start end) 0)
((= count max) 0)
(else (if (timed-prime-test start)
(search-for-primes-impl (+ start 1) (+ count 1))
(search-for-primes-impl (+ start 1) count)))))
(search-for-primes-impl start 0))

(search-for-primes   1000   10000 3)
(search-for-primes  10000  100000 3)
(search-for-primes 100000 1000000 3)

### sicp exercise 1.22

;  Exercise 1.22. Most Lisp implementations include a primitive called runtime that returns an integer
;  that specifies the amount of time the system has been running (measured, for example, in microseconds).
;  The following timed-prime-test procedure, when called with an integer n, prints n and checks to see
;  if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time
;  used in performing the test.
;    (define (timed-prime-test n)
;       (newline)
;       (display n)
;       (start-prime-test n (runtime)))
;    (define (start-prime-test n start-time)
;       (if (prime? n)
;       (report-prime (- (runtime) start-time))))
;    (define (report-prime elapsed-time)
;       (display " *** ")
;       (display elapsed-time))
;  Using this procedure, write a procedure search-for-primes that checks the primality of consecutive
;  odd integers in a specified range. Use your procedure to find the three smallest primes larger than
;  1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test
;  each prime.  Since the testing algorithm has order of growth of O(sqrt(n)), you should expect that testing
;  for primes around 10,000 should take about sqrt(10) times as long as testing for primes around 1000.
;  Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the sqrt(n)
;  prediction? Is your result compatible with the notion that programs on your machine run in time
;  proportional to the number of steps required for the computation?

(define (runtime) (gettimeofday))
(define (difftime start end) (+ (* (- (car end) (car start)) 100000) (- (cdr end) (cdr start))))

(define (smallest-divisor n)
(define (square number) (* number number))
(define (divides? n divisor) (= (remainder n divisor) 0))
(define (find-divisor n divisor)
(cond ((> (square divisor) n) n)
((divides? n divisor) divisor)
(else (find-divisor n (+ divisor 1)))))
(find-divisor n 2))

(define (prime? n) (= (smallest-divisor n) n))

(define (timed-prime-test n) (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (difftime start-time (runtime)))
#f))

(define (report-prime n elapsed-time)
(display n)
(display " *** ")
(display elapsed-time)
(newline)
#t)

;(timed-prime-test 3)

(define (search-for-primes start end max)
(define (search-for-primes-impl start count)
(cond ((> start end) 0)
((= count max) 0)
(else (if (timed-prime-test start)
(search-for-primes-impl (+ start 1) (+ count 1))
(search-for-primes-impl (+ start 1) count)))))
(search-for-primes-impl start 0))

(search-for-primes   1000   10000 3)
(search-for-primes  10000  100000 3)
(search-for-primes 100000 1000000 3)

### sicp exercise 1.21

; Exercise 1.21. Use the smallest-divisor procedure to find the smallest divisor of each of the
; following numbers: 199, 1999, 19999.

(define (smallest-divisor n)
(define (square number) (* number number))
(define (divides? n divisor) (= (remainder n divisor) 0))
(define (find-divisor n divisor)
(cond ((> (square divisor) n) n)
((divides? n divisor) divisor)
(else (find-divisor n (+ divisor 1)))))
(find-divisor n 2))

(display (smallest-divisor 10)) (newline)
(display (smallest-divisor 199)) (newline)
(display (smallest-divisor 1999)) (newline)
(display (smallest-divisor 19999)) (newline)

## Friday, June 27, 2008

### sicp exercise 1.19

;  Exercise 1.19. There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number
;  of steps. Recall the transformation of the state variables a and b in the fib-iter process of section
;  1.2.2: a <-- a + b and b <-- a. Call this transformation T, and observe that applying T over and over
;  again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the
;  Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with
;  the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations
;  Tpq, where Tpq transforms the pair (a,b) according to a <-- bq + aq + ap and b <-- bp + aq.
;  Show that if we apply   such a transformation Tpq twice, the effect is the same as using a single
;  transformation Tp'q' of the same form, and compute p' and q' in terms of p and q. This gives us an
;  explicit way to square these transformations, and thus we can compute Tn using successive squaring,
;  as in the fast-expt procedure.  Put this all together to complete the following procedure, which runs
;  in a logarithmic number of steps
;
;
; (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
;                 <??> ; compute p'
;                 <??> ; compute q'
;                 (/ count 2)))
;     (else (fib-iter (+ (* b q) (* a q) (* a p))
;                     (+ (* b p) (* a q))
;                     p
;                     q
;                     (- count 1)))))

;
;  p' = p^2 + q^2
;  q' = q^2 + 2pq
;

(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
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))

(display (fib 1)) (newline)
(display (fib 2)) (newline)
(display (fib 3)) (newline)
(display (fib 4)) (newline)
(display (fib 5)) (newline)
(display (fib 6)) (newline)
(display (fib 7)) (newline)
(display (fib 8)) (newline)
(display (fib 9)) (newline)
(display (fib 10)) (newline)
(display (fib 11)) (newline)
(display (fib 12)) (newline)
(display (fib 5000)) (newline)