Chapter 1 Solution detail

Exercise 1.1

#!scheme
10
; => 10

(+ 5 3 4)
; => 12

(- 9 1)
; => 8

(/ 6 2)
; => 3

(+ (* 2 4) (- 4 6))
; => 6

(define a 3)
; => a

(define b (+ a 1))
; => b

(+ a b (* a b))
; => 19

(= a b)
; => #f

(if (and (> b a) (< b (* a b)))
    b
    a)
; => 4

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
; => 16

(+ 2 (if (> b a) b a))
; => 6

(* (cond ((> a b) a)
     (( < a b) b)
     (else -1))
   (+ a 1))
; => 16

Exercise 1.2

#!scheme
(/ (+ 5 4
      (- 2
     (- 3 (+ 6 (/ 4 5)))))
   (* 3
      (- 6 2)
      (- 2 7)))
; => -37/150

Exercise 1.3

#!scheme
(define (large-two-sum-square a b c)
  (define (sum-of-square a b c)
    (+ (square a) (square b) (square c)))
  (define (smallest a b c)
    (cond ((and (<= a b) (<= a c)) a)
      ((and (<= b a) (<= b c)) b)
      (else c)))
  (- (sum-of-square a b c) (square (smallest a b c))))

(large-two-sum-square 1 3 4)
; => 25
(large-two-sum-square 7 3 4)
; => 65

Exercise 1.4

#!scheme
(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

(a-plus-abs-b 3 -1)
; => 4
(a-plus-abs-b 3 5)
; => 8

Exercise 1.4 show that compound expression can be manipulated just as primitive expression. So function and compound procedure are first class citizen. It can be passed to or returned as functions' parameters.

Exercise 1.5

See Chapter keypoint for detail explanation.

Exercise 1.6

See Chapter keypoint for detail explanation.

Exercise 1.7

For very small value, the absolute tolerance of 0.001 is very large when computing the square roots of a small value. The following is a example showing of compute sqrt of small value :

#!scheme
(sqrt 0.001)
; => .04124542607499115
(sqrt 0.0001)
; => .03230844833048122
(sqrt 0.0000001)
; => .03230844833048122
(sqrt 1e60)
; => not terminated

We can see that the second and third result is same, in fact, the third is a wrong answer.

On the other hand, for large value of parameter, we should notice that in actually computer, it use IEEE floating point to store float number. So if the number is extremely large, the machine precision is unable to represent small difference between large number, so the algorithm never terminates. As show in the forth example above.

An improved version of the sqrt procedure can be implement as follow:

#!scheme
(define (good-enough-enhance? guess x)
  (< (abs (- (improve guess x) guess))
     (* guess 0.001)))

(define (sqrt-iter-enhance guess x)
  (begin
    (display guess)
    (newline)
    (if (good-enough-enhance? guess x)
    guess
    (sqrt-iter-enhance (improve guess x) x))))

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

(sqrt-enhance 0.0000001)
;Value: 3.162477562740737e-4

(sqrt-enhance 1e60)
;Value: 1.0000788456669446e30

the good-enough-enhance? does not use absolute tolerance but use relative tolerance to determin the terminated of the procedure. So does not have the problem as before.

Exercise 1.8

#!scheme
(define (cube-improve guess x)
  (/ (+ (/ x (square guess)) (* 2 guess))
     3))

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

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

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

(cube-root 27)
;Value: 3.001274406506175

Exercise 1.9

#!scheme
(define (add a b)
  (if (= a 0) b (inc (add (dec a) b))))

apply the above procedure (add 4 5) will generate the following substitution

#!scheme
(inc (add (dec 4) 5))
(inc (inc (add (dec 3) 5)))
(inc (inc (inc (add (dec 2) 5))))
(inc (inc (inc (inc (add (dec 1) 5)))))
(inc (inc (inc (inc (add 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

So this is a recursive call.

#!scheme
(define (add a b)
  (if (= a 0) b (add (dec a) (inc b))))

The other one will generate substitution as follows:

#!scheme
(add (dec 4) (inc 5))
(add (dec 3) (inc 6))
(add (dec 2) (inc 7))
(add (dec 1) (inc 8))
(add 0 9)
9

Exercise 1.10

Definition of Ackermann's function.

#!scheme
(define (A x y)
  (cond ((= y 0) 0)
    ((= x 0) (* 2 y))
    ((= y 1) 2)
    (else (A (- x 1) (A x (- y 1))))))

(A 1 10)
;Value: 1024

(A 2 4)
;Value: 65536

(A 3 3)
;Value: 65536

Define (define (f n) (A 0 n)), (define (g n) (A 1 n)), (define (h n) (A 2 n)), use simple mathematical calculuation, we will know that (f n) is 2*n, (g n) is 2^n and (h n) is 2^{2^{2^...}}(n times).

Exercise 1.11

#!scheme
(define (f-rec n)
  (if (< n 3)
      n
      (+ (f-rec (- n 1)) (* 2 (f-rec (- n 2))) (* 3 (f-rec (- n 3))))))

(f-rec 4)
;Value: 11

(define (f num)
  (define (f-iter a b c count)
    (if (= count 0)
    a
    (f-iter b c (+ (* 3 a) (* 2 b) c) (- count 1))))
  (f-iter 0 1 2 num))

(f 4)
;Value: 11

Exercise 1.12

#!scheme
;; compute combination number C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
(define (combinate-rec k n)
  (cond ((= k 1) n)
    ((= k n) 1)
    (else (+ (combinate-rec (- k 1) (- n 1))
         (combinate-rec k (- n 1))))))

(combinate-rec 2 4)
;Value: 6

(combinate-rec 4 10)
;Value: 210

Exercise 1.13

Any book about Discrete mathematics will talk about the solve of this recursive formula.

Exercise 1.14

See this page for the solution.

Exercise 1.15

#!scheme
(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (my-sin angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (my-sin (/ angle 3.0)))))

(my-sin 12.15)
;Value: -.39980345741334

(sin 12.15)
;Value: -.4044438228491401

It can be seen that there is small difference between the system sin function's answer and the answer of the code of the exercise. But still a good approximation.

evalutea (my-sin 12.15) will generate the following call

#!scheme
(my-sin 12.15)
(p (my-sin 4.05))
(p (p (my-sin 1.35)))
(p (p (p (my-sin 0.45))))
(p (p (p (p (my-sin 0.15))))
(p (p (p (p (p (my-sin 0.05)))))
(p (p (p (p (p 0.05)))))

so it will call procedure p five time.

Exercise 1.19

#!scheme
(define (fast-fib n)
  (fast-fib-iter 1 0 0 1 n))

(define (fast-fib-iter a b p q count)
  (cond ((= count 0) b)
    ((even? count)
     (fast-fib-iter a
            b
            (+ (square p) (square q))
            (+ (* 2 p q) (square q))
            (/ count 2)))
    (else (fast-fib-iter (+ (* b q) (* a q) (* a p))
                 (+ (* b p) (* a q))
                 p
                 q
                 (- count 1)))))

(fast-fib 0)
;Value: 0
(fast-fib 1)
;Value: 1
(fast-fib 2)
;Value: 1
(fast-fib 3)
;Value: 2
(fast-fib 4)
;Value: 3
(fast-fib 5)
;Value: 5

See Chapter-01-keypoint for detail.

Exercise 1.21

#!scheme
(smallest-divisor 199)
; Value:  199
(smallest-divisor 1999)
; Value: 1999
(smallest-divisor 19999)
; Value: 7

Exercise 1.22

#!scheme
(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))

(timed-prime-test 1013)

(define (search-for-primes start end)
  (cond ((> start end) 'Done)
    (else (begin
        (timed-prime-test start)
        (search-for-primes (+ 1 start) end)))))

(search-for-primes 1001 1019)
(search-for-primes 10001 10019)
(search-for-primes 100001 100019)

(search-for-primes 1000001 1000019)

(search-for-primes 1000000001 1000000019)
(search-for-primes 100000000001 100000000019)

Exercise 1.23

#!scheme
(define (smallest-divisor n) (find-divisor n 2))

(define (find-divisor n test-divisor)
  (define (next-divisor n)
    (cond ((= n 2) 3)
      (else (+ n 2))))
  (cond ((> (square test-divisor)n )n)
    ((divides? test-divisor n) test-divisor)
    (else (find-divisor n (next-divisor test-divisor)))))

(define (divides? a b) (= (remainder b a) 0))

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

(smallest-divisor 23)

Exercise 1.27

#!scheme
(define (test-carmichael num)
  (define (work a)
    (cond ((= a num) #t)
      (else (and (= a (expmod a num num)) (work (+ a 1))))))
  (work 1))

(test-carmichael 561)
;Value: #t
(test-carmichael 1105)
;Value: #t
(test-carmichael 1729)
;Value: #t
(test-carmichael 2465)
;Value: #t
(test-carmichael 2821)
;Value: #t
(test-carmichael 6601)
;Value: #t
(test-carmichael 540)
;Value: #f
(test-carmichael 530)
;Value: #f

Exercise 1.28

#!scheme
(define (expmod base exp m)
  (define (nontrivial? num n)
    (and (not (= num 1)) (not (= num (- n 1))) (= (remainder (square num) n) 1)))
  (cond ((= exp 0) 1)
    ((even? exp) (if (nontrivial? (expmod base (/ exp 2) m) m)
             (remainder (square (expmod base (/ exp 2) m)) m)
             0))
    (else
     (remainder (* base (expmod base (- exp 1) m)) m))))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
    ((miller-rabin-test n) (miller-rabin-test? n (- times 1)))
    (else false)))

(fast-prime? 561 10)
;Value: #f

(fast-prime? 2821 20)
;Value: #f

See Chapter-01-keypoint for detailed explanation.

Exercise 1.29

#!scheme
(define (integral-simpson f a b n)
  "n must be an even number"
  (define y0 (f a))  ; no good style in practice in FP, see section 1.1.8 for detail
  (define yn (f b))  ; same as above
  (define h (/ (* 1.0 (- b a)) n))
  (define (term-simpson ind)
    (* (cond ((or (= ind 0) (= ind n)) 1)
         ((= (remainder ind 2) 1) 4)
         (else 2))
       (f (+ a (* ind h)))))
  (/ (* h (sum-common term-simpson 0 inc n)) 3))

(integral-simpson cube 0 1 100)
;Value: .24999999999999992

(integral cube 0 1 0.01)
;Value: .24998750000000042

Exercise 1.30

#!scheme
(define (integral-simpson f a b n)
  "n must be an even number"
  (define y0 (f a))  ; no good style in practice in FP, see section 1.1.8 for detail
  (define yn (f b))  ; same as above
  (define h (/ (* 1.0 (- b a)) n))
  (define (term-simpson ind)
    (* (cond ((or (= ind 0) (= ind n)) 1)
         ((= (remainder ind 2) 1) 4)
         (else 2))
       (f (+ a (* ind h)))))
  (/ (* h (sum-common term-simpson 0 inc n)) 3))

(integral-simpson cube 0 1 100)
;Value: .24999999999999992

(integral cube 0 1 0.01)
;Value: .24998750000000042

Exercise 1.31

#!scheme
(define (product term a next b)
  (if (> a b)
      1
      (* (term a) (product term (next a) next b))))

(define (factorial n)
  (product identity 1 inc n))

(factorial 5)
;Value: 120

(define (one-forth-pi up-bound)
  (define (term a)
    (/ (* 1.0 (- a 1) (+ a 1)) (* 1.0 a a)))
  (define (next a)
    (+ a 2))
  (product term 3 next up-bound))

(one-forth-pi 10000)
;Value: .7854374342873239

(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
    result
    (iter (next a) (* result (term a)))))
  (iter a 1))

Exercise 1.32

#!scheme
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a) (accumulate combiner null-value term (next a) next b))))

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

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

(sum-acc cube 1 inc 10)
;Value: 3025

(sum-acc identity 1 inc 100)
;Value: 5050

(define (fact-acc n)
  (product-acc identity 1 inc n))

(fact-acc 5)
;Value: 120

Exercise 1.33

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

(define (square-prime a b)
  (filtered-accumulate + 0 prime? square a inc b))

(square-prime 1 10)
;Value: 88

(define (product-all-relative-prime n)
  (define (test a)
    (= (gcd a n) 1))
  (filtered-accumulate * 1 test identity 1 inc n))

(product-all-relative-prime 6)
;Value 5
(product-all-relative-prime 10)
;Value 189

Exercise 1.34

#!scheme
(define (f g) (g 2))

(f square)

(f (lambda (z) (* z (+ z 1))))

(f f)
;The object 2 is not applicable.
;To continue, call RESTART with an option number:
; (RESTART 2) => Specify a procedure to use in its place.
; (RESTART 1) => Return to read-eval-print level 1.

Exercise 1.35

#!scheme
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
;Value: 1.6180327868852458

Exercise 1.36

#!scheme
(define (fixed-point-print f first-guess)
  (define (close-enough? a b)
    (< (abs (- a b)) tolerance))
  (define (try guess)
    (newline)
    (display guess)
    (let ((next (f guess)))
      (if (close-enough? next guess)
      next
      (try next))))
  (try first-guess))

(fixed-point-print (lambda (x) (/ (log 1000) (log x))) 2.0)

;; the following is output
2.
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
;Value: 4.555532270803653

Exercise 1.37

#!scheme
(define (cont-frac n d k)
  (define (help j)
    (if (= j k)
    (/ (n j) (d j))
    (/ (n j) (+ (d j) (help (+ j 1))))))
  (help 1))

(cont-frac (lambda (i) 1.0)
       (lambda (i) 1.0)
       20)
;Value: .6180339901755978

(define (cont-frac-iter n d k)
  (define (help ans j)
    (if (= j 1)
    (/ (n j) (+ (d j) ans))
    (help (/ (n j) (+ (d j) ans)) (- j 1))))
  (help 0 k))

(cont-frac-iter (lambda (i) 1.0)
        (lambda (i) 1.0)
        20)
;Value: .6180339850173578

Exercise 1.38

#!scheme
(define (d i)
  (if (= (modulo (- i 2) 3) 0)
      (* 2.0 (/ (+ i 1) 3))
      1.0))

(define (n i) 1.0)

(+ 2 (cont-frac n d 20)) 
;Value: 2.7182818284590452

(+ 2 (cont-frac-iter n d 20))
;Value: 2.718281828459045

Exercise 1.39

#!scheme
(define (tan-cf x k)
  (cont-frac (lambda (i)
           (if (= i 1) x (- (square x))))
         (lambda (i)
           (- (* 2 i) 1))
         k))
(tan-cf 0.718 20)
;Value: .8019292202760321

(tan-cf 0.0 20)
;Value: 0

(tan-cf 0.785 30)
;Value: .9992039901050428

Exercise 1.40

#!scheme
(define (cubic a b c)
  (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))

(newtons-method (cubic 1 3 -2) 1.0)
;Value: .5259574806492973

Exercise 1.41

#!scheme
(define (double f)
  (lambda (x)
    (f (f x))))

(define (inc x) (+ x 1))

((double inc) 1)
;Value: 3

(((double (double double)) inc) 5)
;Value: 21

Exercise 1.42

#!scheme
(define (compose f g)
  (lambda (x) (f (g x))))

((compose square inc) 6)
;Value: 49

Exercise 1.43

#!scheme
(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

((repeated square 2) 5)
;Value: 625

Exercise 1.44

#!scheme
(define (smooth f)
  (lambda (x)
    (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))

((smooth square) 5)
;Value: 25.000000000066663

(define (smooth-n n)
  (repeated smooth n))

(((smooth-n 2) square) 5)
;Value: 25.00000000013333

(((smooth-n 4) square) 5)
;Value: 25.000000000266667

Exercise 1.45

Can view the discuss of convergence of fixed point function, and will easily get the result that, it needs ceil(log_2(n)) times of average-damp to make the root of nth power convergence.

Exercise 1.46

#!scheme
(define tolerance 0.0001)

(define (close-enough? x y)
  (< (/ (abs (- x y)) y) tolerance))

(define (iterative-improve good-enough? improve)
  (lambda (x)
    (let ((guess (improve x)))
      (if (good-enough? guess x)
      guess
      ((iterative-improve good-enough? improve) guess)))))

(define (sqrt-ii x)
  ((iterative-improve close-enough? (lambda (y) (average y (/ x y)))) 1.0))

(sqrt-ii 4)
;Value: 2.000000000000002

(define (fixed-point-ii f first-guess)
  ((iterative-improve close-enough? f) first-guess))

(fixed-point (lambda (y) (average y (/ 4.0 y))) 1.0)
;Value: 2.000000000000002