SICP q1.45

gistfile1.scm

; p.41のcube-rootを参考にコピペ

(define (fixed-point f first-guess)
  (define tolerance 0.00001)
  (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 (average-damp f)
  (define (average a b) (/ (+ a b) 2))
  (lambda (x) (average x (f x))))

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


(print (nth-root 100 2))
(print (nth-root 1000 3))
; (print (nth-root 10000 4))  ; 出ない
(newline)



; 平均緩和（average-damp）の平均緩和を使いたいので
; average-damp を (repeated average-damp 2) 変更
(load "./q1.43")
(define (nth-root x n)
  (fixed-point ((repeated average-damp 2)
                 (lambda (y) (/ x (expt y (- n 1)))))
               1.0))

(print (nth-root 10000 4))
(newline)
(print (nth-root 100000 5))
(newline)
(print (nth-root 1000000 6))
(newline)
(print (nth-root 10000000 7))
(newline)
;(print (nth-root 100000000 8))  ; 出ない
(newline)


; 平均緩和を何回やったら良いかを考えるためにラップ
(define (nth-root-repeat x n repeat-count)
  (define (nth-root x n)
    (fixed-point ((repeated average-damp repeat-count)
                  (lambda (y) (/ x (expt y (- n 1)))))
                 1.0))
  (nth-root x n))


(print (nth-root-repeat 100 2 1))
(newline)
(print (nth-root-repeat 1000 3 1))
(newline)
;(print (nth-root-repeat 10000 4 1))  ; 出ない
(print (nth-root-repeat 10000 4 2))
(newline)
(print (nth-root-repeat (expt 10 5) 5 2))
(newline)
(print (nth-root-repeat (expt 10 6) 6 2))
(newline)
(print (nth-root-repeat (expt 10 7) 7 2))
(newline)
;(print (nth-root-repeat (expt 10 8) 8 2)) ; 出ない
(print (nth-root-repeat (expt 10 8) 8 3))
(newline)
(print (nth-root-repeat (expt 10 9) 9 3))
(newline)
(print (nth-root-repeat (expt 10 10) 10 3))
(newline)
(print (nth-root-repeat (expt 10 11) 11 3))
(newline)
(print (nth-root-repeat (expt 10 12) 12 3))
(newline)
(print (nth-root-repeat (expt 10 13) 13 3))
(newline)
(print (nth-root-repeat (expt 10 14) 14 3))
(newline)
(print (nth-root-repeat (expt 10 15) 15 3))
(newline)
;(print (nth-root-repeat (expt 10 16) 16 3)) ; 出ない
(print (nth-root-repeat (expt 10 16) 16 4))
(newline)

; 4->1, 8->2, 16->3 ... なので32->4は出なそう
(print (nth-root-repeat (expt 10 31) 31 4))
;(print (nth-root-repeat (expt 10 32) 32 4)) ; 出ない
(newline)

; つまり、
; nが2^2-1までならaverage-dampを1回でよい
; nが2^2ならaverage-dampを2回必要
; nが2^3-1までならaverage-dampを2回でよい
; nが2^3ならaverage-dampを3回必要
; nが2^4-1までならaverage-dampを3回でよい
; nが2^4ならaverage-dampを4回必要
; ...
; nが2^t-1までならaverage-dampをt-1回で良い
; nが2^tならaverage-dampをt回必要
(print (log 2 2)) ; 1.0
(print (log 4 2)) ; 2.0
(print (log 8 2)) ; 3.0
(print (log 16 2)) ; 4.0
(newline)

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

(print (nth-root (expt 10 4) 4))
(print (nth-root (expt 10 8) 8))
(print (nth-root (expt 10 16) 16))
(print (nth-root (expt 10 32) 32))