sicp-exercise-1.44-1.46

Exercise 1.44

(define (average a b c) ;there should be a general way to get average
  (/ (+ a b c) 3.0))

(define (smooth f)
  (lambda (x)
    (average (f x)
             (f (- x 0.5))
             (f (+ x 0.5)))))

(define (n-fold-smooth f n)
    (repeated (smooth f) n))

I need to check my answer through some examples, will find some later.

Exercise 1.45

(define (nth-root x n damp-times)
  (find-fixed-points ((repeated average-damp (damp-times n))
                      (lambda (y) (/ x (fast-expt y (- n 1)))))
                     1.0))

damp time should be n/2
(define (half n) (/ n 2))
But how to cast n to integer, in case I receive a float number?

And yet, it doesn't work that well:
;1 ]=> (nth-root 32 5 half)
;Aborting!: out of memory

Exercise 1.46

iterative-improve return a procedure built from its two parameters good-enough? and improve-guess. The returned procedure iteratively improves the guess until good enough.

(define (iterative-improve good-enough? improve-guess)
  (define (get-guess guess)
    (if (good-enough? guess)
      guess
      (get-guess (improve-guess guess))))
  get-guess)

(define (iter-improve-sqrt x)
  ((iterative-improve (lambda (guess)
                       (< (abs (- (square guess) x))
                          0.01))
                      (average-damp (lambda (y) (/ x y))))
   1.0))

(define (close-enough? v1 v2)
  (< (abs (- v1 v2)) 0.00001))

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

sicp-exercise-1.44-1.46

Exercise 1.43

(define (average a b c) ;there should be a general way to get average
  (/ (+ a b c) 3.0))

(define (smooth f)
  (lambda (x)
    (average (f x)
             (f (- x 0.5))
             (f (+ x 0.5)))))

(define (n-fold-smooth f n)
    (repeated (smooth f) n))

I need to check my answer through some examples, will find some later.

LinuxBuaa getting together

This evening, members from our google group LinuxBuaa got together in a small restaurant near out school.

It's our first meeting, but things went on quite well. We talked about the idea to set up a Linux user group in Beihang, general situation of open source in our college. Several guys want a powerful music player on Linux, something like foobar2000. They might join such projects or even start a new one. Some talked about their own projects, like Ran Jiao's compiler. I promoted Gnome-
Asia summit there, and I even got four volunteers!

Open source still has a long way to go to get a wide user base. And open source in China needs more code, more CODE! not just USE.

We must think more about the purpose, operating mode, and everything else of that Linux user group, to really set it up. Long way to go, but I already see much help along the way :)

sicp-exercise-1.40-1.43

Exercise 1.40

I think this exercise is just to let me write a procedure returning another procedure, right?
cubic takes three parameters as those coefficients, and returns a procedure which takes one parameter.

(define (cubic a b c)
  (lambda (x) (+ (cube x)
                 (* a (square x))
                 (* b x)
                 c)))

Exercise 1.41

(define (double f)
  (lambda (x) (f (f x))))

The value of (((double (double double)) inc) 5) is 21.
This is how I analyze it,
(double (double double)) will perform as, (yes, it's like normal order evaluation, but they say the results are the same with normal and applicative)
((double double) (double double))
(double double) means applying four times; in the expression above, the second (double double), as operand, applies inc four times, and the first (double double) applies this four-times-inc four times. So adding 16 to 5, generating 21.

Exercise 1.42

(define (compose f g)  (lambda (x) (f (g x))))

Exercise 1.43

(define (repeated func times)
  (define (nth-repeat result n)
    (if (= n 1)
      result
      (nth-repeat (compose func result)
                  (- n 1))))
  (nth-repeat func times))

My first attemp not using the hint:

(define (repeated func times)
  (define (nth-repeat result n)
    (if (= n 1)
      result
      (nth-repeat (lambda (x)
                    (func (result x)))
                  (- n 1))
  (nth-repeat func times))))

I forgot about the hint, so it takes me some time here,previously I get this error:
;The object #[compound-procedure 1 inc], passed as the first argument to integer-add, is not the correct type.
--Because I wrote things like (nth-repeat (func result))
but, it's in fact not hard, since the func always takes one argument, which of course shouldn't be a procedure; I must apply (result x) first, and supply its result to func.
The lesson is, abstraction can help, at least make it easier to think clear.

sicp-exercise-1.35-1.39

Exercise 1.35

(define (cal-golden-ratio)
  (find-fixed-points (lambda (x) (+ 1 (/ 1 x)))
                     1.0))

Exercise 1.36

(define (find-fixed-points f x)
  (let ((next-guess (f x)))
    (cond ((close-enough? x next-guess) x)
          (else (newline)
                (display x)
                (find-fixed-points f next-guess)))))

(find-fixed-points (lambda (x) (/ (log 1000)
                                  (log x)))
                   2)

>>

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
4.555532270803653
4.555537970114198
4.555534211524127
4.555536690243655
4.555535055574168
4.5555361336081
4.555535422664798
4.5555358915186215
4.555535582318266
4.555535786230128

(find-fixed-points (lambda (x) (average x
                                        (/ (log 1000)
                                           (log x))))
                   2)

>> far fewer steps

2
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825
4.555536019631145


Exercise 1.37
Iterative one, Calculating from inner-most outward.

(define (cont-frac N D k)
  (define (iter ix result)
    (if (= ix 0)
      result
      (iter (- ix 1.0)
            (/ (N ix)
               (+ (D ix) result)))))
  (iter k 0))

Recursive one. Calculating from out-most inward.

(define (cont-frac N D k)
  (define (aux ix)
    (if (> ix k)
      0
      (/ (N ix)
         (+ (D ix)
            (aux (+ ix 1))))))
  (aux 1))

(display (/ 1.0
            (cont-frac (lambda (x) 1.0)
                       (lambda (x) 1.0)
                       12)))

k=12 is ok, accurate to 4 decimal places, 1.6180

Exercise 1.38

Observe that

Di =
1               if i%3 = 0 or 1
2*((i + 1)/3)   if i%3 = 2

(define (euler-expansion)
  (cont-frac (lambda (x) 1.0)
             (lambda (i)
               (let ((rem (remainder i 3)))
                 (if (= rem 2)
                   (* 2 (/ (+ i 1) 3))
                   1)))
             10))

10-term recursive can do the job well, generating 2.71828171 (e=2.71828183)

Exercise 1.39

Noticing Ni can be expressed as, x, -x^2, -x^2, -x^2, J.H.Lambert's formula can be evaluated as a finite continued fraction.

(define (tan-cf x)
  (cont-frac (lambda (i) (if (= i 1)
                             x
                             (- (square x))))
             (lambda (i) (- (* 2 i) 1))
             10))

sicp-exercise-1.34

Exercise 1.34

>> (f f)
>> g = f now, (g 2) ==> (f 2)
>> g = 2 now, (g 2) ==> (2 2)
>> ==> error: The object 2 is not applicable.

sicp-exercise-1.32-1.33

Exercise 1.32

Recursive process

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

Iterative process

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

Define sum and product.

(define (sum a b term next)
  (define (add x y) (+ x y))
  (accumulate add 0 a b term next))


(define (product a b term next)
  (define (mul x y) (* x y))
  (accumulate mul 1 a b term next))

Exercise 1.33

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

Define sum of the squares of the prime numbers in [a, b],
and product of all positive integers less than n that are relatively prime to n.

(define (sum-prime-squares a b)
  (filtered-accumulate prime? add 0 square a inc b))

;;;;;;;;;;;;;
(define (relative-prime? x y)
  (= (gcd x y) 1))

(define (product-reletive-prime n)
  (define (filter x)
    (relative-prime? x n))
  (filtered-accumulate filter mul 1 identity 1 inc n))

sicp-exercise-1.29-1.31

Exercise 1.29

n should be even

(define (simpson-integral f a b m)
  (define n (* m 1.0))
  (define step (/ (- b a) n))
  (define (next x) (+ x (* 2 step)))
  (* step
     (/ 1.0 3.0)
     (+ (f a)
        (* 2
           (sum (next a) ; even-indexed elements
                (- b (* 2 step))
                f
                 next))
        (* 4
           (sum (+ a step) ; odd-indexed elements
                (- b step)
                f
                next))
        (f b))))

This approach is somewhat ugly, the sequence is divided into even-indexed and odd-indexed, since I don't find a universal pattern.

Exercise 1.30

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

Exercise 1.31

Recursive one

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

Iterative one

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

Use product to define factorial.

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

Compute PI with John Wallis's formula.

(define (wallis-term m)
  (/ (* (* 2.0 m)
        (+ (* 2.0 m) 2.0))
     (square (+ (* 2.0 m) 1.0))))

(define (wallis-formula n)
  (product 1.0 n wallis-term inc))

(* 4.0 (wallis-formula 10000))

sicp-exercise-1.21-1.28

Exercise 1.21

199 and 1999 are prime numbers, and 19999 has smallest divisor of 7.

Exercise 1.22 - 1.24

FIXME
Now on my machine the test always returns zero :( So I have to postpone 1.22-1.24 afterward. (runtime) seems not using microseconds, and even not seconds.

Exercise 1.25

Ms. Hacker is not correct exactly. My first attempt is just like hers, calculating exponentiation and using it to evaluate a^n % m. But this approach fails to get a result in a reasonably short time for input around just ten thousand.

The expmod in the text is based on the fact that,

(a*b) % m = ((a%m) * (b%m)) % m
     = ((a%m) * b) % m
     = (a * (b%m) % m
(a^2) % m = ((a%m)^2) % m

The above equations can be easily seen once you write a,b as
a = km + r1
b = nm + r2

Exercise 1.27

expmod, smallest-divisor and prime? from the text are used.

(define (check a n)
  (cond ((= a n) true)
        ((= (expmod a n n) a) (check (+ a 1) n))
        (else false)))

(define (test-fermat n)
  (display "\n")
  (display n)
  (display "\n")
  (if (prime? n)
    (display "\tis prime\n")
    (display "\tis not prime.\n"))
  (if (check 2 n)
    (display "\tpass fermat test.\n")
    (display "\tfail fermat test.\n")))

Exercise 1.28

I use the special form 'let', since I need a local variable here.
I suppose I can't write defines in cond, although "the part of each cond clause may be a sequence of expressions" (footnote #19), like:

(define (f x)
  (cond ((> x 1)
         (define bar ())
         (define (foo a) ())
         (foo bar))
        ()))

Can I? The error reads: Can't bind name in null syntactic environment. Seems that it's a temporary environment.

(define (nontrivial-sqrt? x n)
  (if (and (= (remainder (square x) n) 1)
           (not (= x 1))
           (not (= x (- n 1))))
    true
    false))

(define (new-expmod base expo mod)
  (cond ((= expo 0) 1)
        ((even? expo) (let ((temp (new-expmod base (/ expo 2) mod)))
                        (if (nontrivial-sqrt? temp mod)
                          0
                          (remainder (square temp) mod))))
        (else (remainder (* base (new-expmod base (- expo 1) mod))
                                 mod))))

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

(define (check-prime n checktimes)
  (cond ((= checktimes 0) true)
        ((miller-rabin-test n) (is-prime? n (- checktimes 1)))
        (else false)))

(define (prime? n)
  (check-prime n 1))

starting a new blog

I have been writing on YculBlog, a Chinese blog website. Thanks so much for them, but now I would like to change to Blogger. Blogger is better. (I only worry that it would be blocked again).

For example, sometimes I write codes on my blog, but I haven't found a way to highlight the codes on YculBlog. So I decided to do the switch, due to this and some other reasons.

I copied some posts from my first blog here, yes, I know it's evil to reinvent the wheel, but..

They are in my list of SICP notes. I have begun reading the Structure and Interpretation of Computer Programs for several weeks now and got the notes online. It will be continued with the better Blogger. Other ancient articles will be left alone.

sicp-section-1.2.2

0.
'In fact, it is not hard to show that the number of times the procedure will
compute (fib 0) or (fib 1) (the number of leaves in the above tree, in
general) is precisely Fib(n+1).'

Proof:

Let r(n) to be the number of leaves in the tree rooted in Fib(n), then it's
easy to see that,

r(n) = r(n-1) + r(n-2) (when n > 1)

( since the tree rooted in Fib(n) has two braches, which are repectively
rooted in Fib(n-1) and Fib(n-2). )

When n is 0 or 1,
r(n) = 1

The above description makes precisely a Fibonacci sequence (1,1,2,3..),
lacking the first element, i.e., r(0) is Fib(1), r(1) is Fib(2), so,

r(n) = Fib(n+1)

1.
FIXME: 'The space required grows only linearly with the input, because we
need keep track only of which nodes are above us in the tree at any point
in the computation.'

2.
FIXME: Come up with the efficient answer to count-change problem.

sicp-exercise-1.20

Exercise 1.20

With normal-order evalutation,

(gcd 206 40)

40 != 0

(gcd 40 (r 206 40))

[(r 206 40) != 0]
=> 1 time

(gcd (r 206 40)
     (r 40
        (r 206 40)))

[(r 40 (r 206 40)) != 0 ]
=> 2 times

(gcd (r 40
        (r 206 40))
     (r (r 206 40)
        (r 40
           (r 206 40))))

(r (r 206 40) (r 40 (r 206 40))) != 0
=> 4 times

(gcd (r (r 206 40)
        (r 40
           (r 206 40)))
     (r (r 40
           (r 206 40))
        (r (r 206 40)
           (r 40
              (r 206 40)))))

(r (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))) == 0
=>  7 times

(r (r 206 40) (r 40 (r 206 40)))
=> 4 times

So remainder is called 18 times

With applicative-order evalutation,

(gcd 206 40)
(gcd 40 6) 1
(gcd 6 4)  1
(gcd 4 2)  1
(gcd 2 0)  1

Remainder is called 4 times

sicp-exercise-1.16-1.19

Exercise 1.16

'In general, the technique to defining an invariant quantity that remains
unchanged from state to state is a powerful way to think about the design of
iterative algorithms.'

1 * b^n
=> 1 * (b^2)^(n/2) (n is even)
=> b * b^(n-1) (n is odd)

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

Exercise 1.17

(define (double a)
  (+ a a))
(define (halve a)
  (/ a 2))

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

Exercise 1.18

a*b
0 + a*b
=> 0 + (2a)*(b/2)
=> b + a*(b-1)

(define (double a)
 (+ a a))

(define (halve a)
 (/ a 2))

(define (mul a b)
 (define (mul-iter m a b)
  (cond ((= b 0) m)
        ((even? b) (mul-iter m (double a) (halve b)))
        (else (mul-iter (+ m a) a (- b 1)))))
 (mul-iter 0 a b)

Exercise 1.19

b is the small one and a is big.

(define (T a b p q n)
 (define (update-p)
   (+ (square p) (square q)))
 (define (update-q)
   (+ (* 2 p q) (square q)))
 (define (trans-a)
   (+ (* b q) (* a q) (* a p)))
 (define (trans-b)
   (+ (* b p) (* a q)))

 (cond ((= n 0) b)
       ((even? n) (T a b (update-p) (update-q) (/ n 2)))
       (else (T (trans-a) (trans-b) p q (- n 1)))))


(define (fib n)
  (T 1 0 0 1 n))

sicp-exercise-1.14-1.15

Exercise 1.14

'Count-change generates a tree-recursion process.'

'In general, the number of steps required by a tree-recursive process will
be proportional to the number of nodes in the tree, while the space required
will be proportional to the maxinum depth of the tree.'

The depth is amount/value-of-smallest-coin.
The number of nodes is FIXME

Exercise 1.15

a.

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))
...

So, when (sine 12.15) is evaluated, p is applied five times.

b.

When (sine a) is evaluated, the number of times p is applied is log(a/0.1)
based on 3, i.e. int( ln(a/0.1) / ln(3) ). So the order of growth can be
written as theta of log(a).

The order of growth in space is the same. (right?)