オンラインSICP読書女子会 #12 (1.3.4)

1.40 newton法

(load "./newtons-method.scm")
(define (cube x) (* x x x))

; 不動点プロセスで x^3 + a*x^2 + b*x + c = 0 の零点の近似値を求める
(define (cubic a b c)
  (lambda (x) (+ (cube x)
		 (* a (square x))
		 (* b x)
		 c)))

(newtons-method (cubic -3 3 -1) 1) ;1.0

1.41 手続きを二回適用する手続き

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

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

((double inc) 1) ; 3
(((double (double double)) inc) 5) ; 21 (+16)

1.42

関数の合成を実装する手続きをcomposeを実装する

x -> f(g(x))

;; 1.42

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

(define (square x) (* x x))
(define (inc x) (+ x 1))
((compose square inc) 6) ;; 49
((compose square inc) 11) ;; 144

1.43

n回fを適用する手続き repeatedを

fがsquareだったら、n回適用すれば引数を2^nする関数になる
f(f(......f(x)))

;; 1.43
(load "./1.42.scm")
(define (inc x) (+ x 1))

(define (repeated func n)
  (if (= n 1)
      func
      (compose func (repeated func (- n 1)))))


((repeated square 2) 5) ;; 625
(time ((repeated inc 10000000) 1))
; real   0.558
; user   0.550
; sys    0.000

;; hioさんの見習う

(define (repeated func n)
  (cond ((= n 1)
	 func)
	((= (remainder n 2) 1)
	 (compose func (repeated func (- n 1))))
	(else
	 (let ((f (repeated func (/ n 2))))
	   (compose f f)))
	))

((repeated square 2) 5) ;; 625
(time ((repeated inc 10000000) 1))
; real   0.552
; user   0.540
; sys    0.000


;; hioさんの末尾再帰版
(define (repeated f n)
  (define (iter i val)
    (if (>= i n)
	val
	(iter (+ i 1) (f val))))
  (lambda (x) (iter 0 x)))
(time ((repeated inc 10000000) 1))
; real   0.476
; user   0.480
; sys    0.000
;; そんな時間かわらないな
;; これだと手続き

1.44

平滑化: dxが小さな値であるとき、 f(x - dx), f(x), f(x + dx) の平均をとったもの
平滑化したものを計算するsmoothの手続きをかけ。
また、n重平滑化関数をrepeatedを使って示す。

;; 1.44
(load "./1.43.scm")

(define (smooth f)
  (define dx 0.0001)
  (lambda (x)
    (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3) ))
  
((smooth square) 2) ;; 4.000000006666666

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

((n-fold-smooth square 4) 2) ;; 65536.00098646007 (2 ^ 16)

1.45 (未解決)

n乗根を求める

source

;; fixed-point
(define tolerance 0.0001)
(define max-recursion 8)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))

  (define (try guess i)
    (print "guess:" i "回目 " guess)
    (let ((next (f guess)))
      (if (or (close-enough? guess next) (= i max-recursion))
	  next
	  (try next (+ i 1)))))
  (try first-guess 1))

(define (average-damp f)
  (lambda (x) (/ (+ (f x) x) 2.0)))


;; 2, 3乗根
(define (nth-root x n)
  (fixed-point
   (average-damp (lambda (y) (/ x (expt y (- n 1))))) 1.0))

;;(print (nth-root 100 2)) ;;10.0
;;(print (nth-root 1000 3)) ;; 10.000002544054729
;; (nth-root 10000 4) ;;無限にfixせず、、、、


;; 4乗根以上
(define (repeated func n)
  (if (= n 1)
      func
      (compose func (repeated func (- n 1)))))

(define (repeated-nth-root x n m)
  (fixed-point
   (repeated (average-damp (lambda (y) (/ x (expt y (- n 1))))) m) 1.0))

(define (try-repeat m n root)
  (define (iter i)
    (print "----------------------------------")
    (print  m " ^ 1 / " root " の" i "重平均緩和")
    (print "----------------------------------")
    (repeated-nth-root m (+ i 1) root)
    (if (= i n)
	0
	(iter (+ i 1))))
  (iter 1))

(print "2のn乗のn乗根をしらべる")

(print "==========================")
(print "2乗根")
(print "==========================")
(try-repeat (expt 2 2) 3 2)

(print "==========================")
(print "3乗根")
(print "==========================")
(try-repeat (expt 2 3) 5 3)

(print "==========================")
(print "4乗根")
(print "==========================")
(try-repeat (expt 2 4) 5 4)

(print "==========================")
(print "5乗根")
(print "==========================")
(try-repeat (expt 2 5) 10 5)

結果

2のn乗のn乗根をしらべる

==========================
2乗根
==========================
----------------------------------
4 ^ 1 / 2 の1重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 2.05
guess:3回目 2.0000000929222947
----------------------------------
4 ^ 1 / 2 の2重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.57
guess:3回目 1.5829814190634435
guess:4回目 1.586291563873137
guess:5回目 1.5871233896905939
guess:6回目 1.5873316181944288
----------------------------------
4 ^ 1 / 2 の3重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.3780000000000001
guess:3回目 1.3781971576084833
guess:4回目 1.3783910746470118
guess:5回目 1.3785818395983083
guess:6回目 1.3787695375836293
guess:7回目 1.3789542505257217
guess:8回目 1.3791360573022022
==========================
3乗根
==========================
----------------------------------
8 ^ 1 / 3 の1重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 2.843780727630285
guess:3回目 2.82842712474619
----------------------------------
8 ^ 1 / 3 の2重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.8914996576441667
guess:3回目 2.0151199754332096
guess:4回目 1.998142301706526
guess:5回目 2.0002326972862416
guess:6回目 1.999970920454376
----------------------------------
8 ^ 1 / 3 の3重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.478337540623817
guess:3回目 1.9239087525290877
guess:4回目 1.5363162465727038
guess:5回目 1.8553689987180662
guess:6回目 1.560512615640326
guess:7回目 1.8244440279220622
guess:8回目 1.575115962052684
----------------------------------
8 ^ 1 / 3 の4重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.28327359906296
guess:3回目 2.227954293124733
guess:4回目 1.2615306050241493
guess:5回目 2.1609515864967843
guess:6回目 1.2706420422133782
guess:7回目 2.192947191071957
guess:8回目 1.2662518335488215
----------------------------------
8 ^ 1 / 3 の5重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.1951167859192295
guess:3回目 2.2691905546161637
guess:4回目 1.1778909647032938
guess:5回目 2.025355582188155
guess:6回目 1.393915404078827
guess:7回目 1.6030012367264348
guess:8回目 1.2279607772464904
==========================
4乗根
==========================
----------------------------------
16 ^ 1 / 4 の1重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 4.002257524798522
guess:3回目 4.0
----------------------------------
16 ^ 1 / 4 の2重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 2.4829963306881875
guess:3回目 2.5174777560877635
guess:4回目 2.5196940687432705
guess:5回目 2.519832846830349
----------------------------------
16 ^ 1 / 4 の3重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.8341723103276433
guess:3回目 1.8527375467627856
guess:4回目 1.8658611343368858
guess:5回目 1.875827463108303
guess:6回目 1.8837545613602775
guess:7回目 1.8902683221588625
guess:8回目 1.895752040837725
----------------------------------
16 ^ 1 / 4 の4重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.4493508391103145
guess:3回目 1.4519931178812753
guess:4回目 1.4536080602027628
guess:5回目 1.4545943546784106
guess:6回目 1.455195179157848
guess:7回目 1.4555603374021737
guess:8回目 1.4557818914922966
----------------------------------
16 ^ 1 / 4 の5重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.2475321803127808
guess:3回目 1.9040376089300204
guess:4回目 1.666016805952454
guess:5回目 3.1599408649420493
guess:6回目 1.4616166208630994
guess:7回目 1.5843404568698387
guess:8回目 1.540218409475213
==========================
5乗根
==========================
----------------------------------
32 ^ 1 / 5 の1重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 5.65697670118682
guess:3回目 5.65685424949238
----------------------------------
32 ^ 1 / 5 の2重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 3.2611793503277537
guess:3回目 3.1722582719630483
guess:4回目 3.1748817299345116
----------------------------------
32 ^ 1 / 5 の3重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 2.464263577716512
guess:3回目 2.3026699635645205
guess:4回目 2.460267138779624
guess:5回目 2.305728778345352
guess:6回目 2.4567770089373733
guess:7回目 2.3084377997602075
guess:8回目 2.4536947950137824
----------------------------------
32 ^ 1 / 5 の4重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.8527388808054341
guess:3回目 2.986203929953016
guess:4回目 1.684603068446882
guess:5回目 2.8502360866346947
guess:6回目 1.6695442360756085
guess:7回目 2.8887323780143497
guess:8回目 1.6735434538049703
----------------------------------
32 ^ 1 / 5 の5重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.4528868735679294
guess:3回目 3.435041945724486
guess:4回目 1.4526447052333216
guess:5回目 3.4265251637273857
guess:6回目 1.4336537993747493
guess:7回目 2.5063074888395556
guess:8回目 1.829979040239805
----------------------------------
32 ^ 1 / 5 の6重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.238771352270022
guess:3回目 1.8227353362149372
guess:4回目 1.9525400393432408
guess:5回目 4.780617424956585
guess:6回目 1.2363480996581633
guess:7回目 1.76652059151728
guess:8回目 1.4114961694924677
----------------------------------
32 ^ 1 / 5 の7重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.1321524709422879
guess:3回目 6.539943947950366
guess:4回目 1.466902719615096
guess:5回目 1.6646927417487603
guess:6回目 4.484304705092539
guess:7回目 1.4331808312190746
guess:8回目 1.8924176928951446
----------------------------------
32 ^ 1 / 5 の8重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.0801710623656842
guess:3回目 5.215018392022435
guess:4回目 3.2415512094000114
guess:5回目 1.5007653145374489
guess:6回目 5.542008185531579
guess:7回目 12.058755661446032
guess:8回目 2.143355616495691
----------------------------------
32 ^ 1 / 5 の9重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.0549588781203105
guess:3回目 2.114424633995316
guess:4回目 1.1136325618984133
guess:5回目 16.786757179080805
guess:6回目 9.27611486764099
guess:7回目 2.2729115607246606
guess:8回目 2.008299076235135
----------------------------------
32 ^ 1 / 5 の10重平均緩和
----------------------------------
guess:1回目 1.0
guess:2回目 1.0427412930632205
guess:3回目 1.3213126383907263
guess:4回目 8.168781903627231
guess:5回目 5.996862265689423
guess:6回目 6.317346815038818
guess:7回目 12.877405341365169
guess:8回目 29.6151176920096

2乗根：1重平均緩和
というのが最初にわかっていた内容
3乗根：2重平均緩和(あれ、SICPによると1重平均緩和でできるはず・・・
4乗根は、3重の平均緩和でそれらしい値になる (あれ、SICPによると2重平均緩和でできるはず・・・
5乗根は無理じゃないか・・・

repeatのn回目nの数え方がおかしい？
わからなすぎてギブアップ＼(^o^)／

1.46

十分になるまで改善を繰り返すような手続き(反復改良法)を返す手続き

(define (iterative-improve improve enough?)
  (lambda (guess)
    (define (iter guess)
      (if (enough? guess)
	  guess
	  (iter (improve guess))))
    (iter guess)))

;; sqrt
(define (sqrt x)
  (define (enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))

  (define (average x y) (/ (+ x y) 2))
  ((iterative-improve improve enough?) 1.0))

(print "sqrt 2 = " (sqrt 2)) ;; 1.4142156862745097
(print "sqrt 4 = " (sqrt 4)) ;; 2.0000000929222947


;; fix-point
(define (fix-point f first-guess)
  (define (enough? guess)
    (< (abs (- guess (f guess))) 0.00001))
  (f ((iterative-improve f enough?) first-guess)))


;; golden ratio
(define (g x)
  (+ 1 (/ 1 x)))
(print "fix-point golden ratio = " (fix-point g 1.0)) ;;1.6180327868852458

参考 - 問題1.46 – SICP（計算機プログラムの構造と解釈）その24 : Serendip - Webデザイン・プログラミング
ga