SICP学习笔记 1.3.4 过程作为返回值

    练习 1.40

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

1 ]=> (newtons-method (cubic 1.0 1.0 -3.0) 1.0)
;Value: 1.

 

   练习 1.41

(define (double f)
  (lambda (x) (f (f x))))
(define (inc x)
  (+ x 1))
  
1 ]=> (((double (double double)) inc) 5) 
;Value: 21

 

    练习 1.42

(define (compose f g)
  (lambda (x) (f (g x))))
  
1 ]=> ((compose square inc) 6)
;Value: 49

 

   练习 1.43

(define (repeated f n)
  (cond ((= n 1) f)
	((even? n) (compose f (repeated f (/ n 2))))
	(else (compose f (repeated f (- n 1))))))
	
1 ]=> ((repeated square 2) 5)
;Value: 625

 

    练习 1.44

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

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

 

    练习 1.45

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))
1 ]=> (sqrt 4.0)
 *** 1.
 *** 2.5
 *** 2.05
 *** 2.000609756097561
 *** 2.0000000929222947
;Value: 2.000000000000002

(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))
1 ]=> (cube-root 8.0)
 *** 1.
 *** 4.5
 *** 2.447530864197531
 *** 1.8914996576441667
 *** 2.0637643832634476
 *** 1.9710425766479744
 *** 2.0151199754332096
 *** 1.992609760395472
 *** 2.0037362842809587
 *** 1.998142301706526
 *** 2.0009314406381735
 *** 1.9995349299633447
 *** 2.0002326972862416
 *** 1.9998836919616
 *** 2.0000581641656563
 *** 1.999970920454376
 *** 2.0000145404070393
 *** 1.9999927299550464
 *** 2.000003635062117
;Value: 1.9999981824788517

(define (fourth-root x)
  (fixed-point (average-damp (lambda (y) (/ x (cube y)))) 1.0))
  
1 ]=> (fourth-root 16.0)
 *** 1.
 *** 8.5
 *** 4.263026663952778
 *** 2.2347742162681095
 *** 1.8341723103276433
 *** 2.2135774006557023
 *** 1.844363126744897
 ......
 *** 1.983599149847315
 *** 2.016809915138478
 *** 1.983608081177677
 *** 2.0168005353295855
 *** 1.983616997866416
 *** 2.0167911711462776
 *** 1.983625899953568
;Quit!
;; 出现振荡,Ctrl+C杀掉

;; 对x求n次方根时,使用repeated调用m次average-damp(即做m次平均阻尼)

(define (fast-expt x n)
  (fast-expt-iter x n 1))
  
(define (fast-expt-iter x counter product)
  (cond ((= counter 0) product)
	((even? counter) (fast-expt-iter (square x) (/ counter 2) product))
	(else (fast-expt-iter x (- counter 1) (* x product)))))
	
(define (find-root x n m)
  (fixed-point ((repeated average-damp m) (lambda (y) (/ x (fast-expt y (- n 1))))) 1.0))
  
1 ]=> (find-root 4.0 2 1)
 *** 1.
 *** 2.5
 *** 2.05
 *** 2.000609756097561
 *** 2.0000000929222947
;Value: 2.000000000000002

1 ]=> (find-root 8.0 3 1)
 *** 1.
 *** 4.5
 *** 2.447530864197531
 *** 1.8914996576441667
 *** 2.0637643832634476
 *** 1.9710425766479744
 *** 2.0151199754332096
 *** 1.992609760395472
 *** 2.0037362842809587
 *** 1.998142301706526
 *** 2.0009314406381735
 *** 1.9995349299633447
 *** 2.0002326972862416
 *** 1.9998836919616
 *** 2.0000581641656563
 *** 1.999970920454376
 *** 2.0000145404070393
 *** 1.9999927299550464
 *** 2.000003635062117
;Value: 1.9999981824788517

1 ]=> (find-root 16.0 4 2)
 *** 1.
 *** 4.75
 *** 3.5998232249599065
 *** 2.7856139316659103
 *** 2.274263910561008
 *** 2.045743730517053
 *** 2.0015115314098866
 *** 2.000001711389449
;Value: 2.0000000000021965

;; 尝试对求5次方根时做两次平均阻尼以查看收敛性, 可以得到近似正确的结果
1 ]=> (find-root 32.0 5 2)
 *** 1.
 ......
;Value: 2.000001512995761

;; 求6次方根, 做两次平均阻尼仍然能得到正确的近似结果
1 ]=> (find-root 64.0 6 2)
 *** 1.
 ......
;Value: 2.0000029334662086

;; 7次方根
1 ]=> (find-root 128.0 7 2)
......
;Value: 2.0000035538623377

;; 8次方根
1 ]=> (find-root 256.0 8 2)
......
 *** 2.0036413071907813
 *** 1.9964048473987912
 *** 2.0036406355855547
 *** 1.9964055020263292
 *** 2.0036399643510747
 *** 1.9964061562955964  C-c C-c
 *** 2.0036392934869998
;Quit!
;; 出现振荡,Ctrl+C杀掉

;; 在求8次方根时又出现振荡,因此再多做一次平均阻尼,即如下调用,得到正确的近似结果
1 ]=> (find-root 256.0 8 3)
......
;Value: 2.000000000003967

;; 发现如下规律
;; 2、3 次方根时做一次平均阻尼
;; 4、5、6、7 次方根时做两次平均阻尼
;; 8 次方根时做三次平均阻尼
;; 可见对 X 开 N 次方根与做 M 次平均阻尼有如下关系
;; M = (/ (log N) (log 2))
;; 对9、15次方根验证

1 ]=> (find-root 512.0 9 3)
;Value: 1.9999997106840102


1 ]=> (find-root (fast-expt 2.0 15) 15 3)
;Value: 2.0000040951543028

;; 因此修改过程为
(define (find-root x n)
  (let ((m (round (/ (log n) (log 2)))))
    (fixed-point
     ((repeated average-damp m)
      (lambda (y) (/ x
		  (fast-expt y (- n 1))))) 1.0)))

;; 但是继续验证, 发现还有问题  
;; 继续对3^16验证, 做四次平均阻尼仍然会出现振荡, 需要做五次平均阻尼才会得到正确的近似结果
;; 继续对3^32验证, 做六次平均阻尼仍然会出现振荡, 需要做七次平均阻尼才会得到正确的近似结果
;; 继续对3^64验证, 做八次平均阻尼仍然会出现振荡, 需要做十一次平均阻尼才会得到正确的近似结果

;; 于是又发现变化过程
;; 取 K = (/ (log N) (log 2))
;; 取 M = 能得到正确近似结果时需要做的平均阻尼次数
;; K 			M										
;; 1			1
;; 2			2
;; 3 			3
;; 4			5
;; 5 			7
;; 6			11
;; 于是推测
;; 7 			15
;; 漫长的等待后, 终于收敛到了近似结果 ..... -_-|
;; 继续推测
;; 8			21 ?
;; 更加漫长的等待, 不收敛！！！ -_-|
;; 那就试试
;; 8 			23 !
;; MBP MD102 主频i7 2.9 内存8G 跑了近10分钟才收敛到近似结果 -_-|
;; 再往后收敛时间太过漫长, 没有继续测试, 应该有简单的办法可以得到求N次方根与做M次平均阻尼的关系

 

    练习 1.46

;; 对iterative-improve过程的实现
(define (iterative-improve good-enough? improve)
  (define (iter guess)
    (if (good-enough? guess)
			guess
			(iter (improve guess))))
  (lambda (guess) (iter guess)))
  
;; 根据iterative-improve过程对sqrt重新实现
(define (iterative-improve-sqrt x)
  (define (sqrt-good-enough? guess)
    (< (abs (- (square guess) x)) tolerance))
  (define (sqrt-improve guess)
    (average guess (/ x guess)))
  ((iterative-improve sqrt-good-enough? sqrt-improve) 1.0))
  
1 ]=> (iterative-improve-sqrt 9.0)

;Value: 3.000000001396984

;; 根据iterative-improve过程对fixed-point重新实现
(define (iterative-improve-fixed-point f)
   (define (fixed-point-good-enough? guess)
     (< (abs (- guess (f guess))) tolerance))
   ((iterative-improve fixed-point-good-enough? f) 1.0))
   
1 ]=> (iterative-improve-fixed-point cos)

;Value: .7390893414033928

;; 计算结果与原始fixed-point过程计算结果精度略低, 经查
1 ]=> (cos 0.7390893414033928)

;Value: .7390822985224023

;; 即原始fixed-point过程中定义了
let ((next (f guess)))

;; 即对于guess, 原始过程经过next处理后进行检测, 如果足够好返回的是(f guess)
;; 而iterative-improve过程对于guess无此处理, 返回的是guess