暇シリーズ

暇すぎて復習が捗りすぎぃｗ

問題 1.45

(define nil '())

(define (average x y)
  (/ (+ x y) 2))

(define (square x)
  (* x x))

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

;;

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (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)
  (lambda (x) (average x (f x))))

;;

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

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

;;

(define (sqrt x)
  (root-n 2 x))

(define (cbrt x)
  (root-n 3 x))

(define (root-n n x)
  (if (<= n 1)
      x
      (let* ((repeate-count (floor (log n 2)))
             (transform (repeated average-damp repeate-count)))
        (fixed-point (transform (lambda (y) (/ x (expt y (- n 1)))))
                     1.0))))

n 乗根を計算するのに必要な平均緩和の回数は、

です。

gosh> (map (lambda (x) (root-n x (expt x x))) (enumerate-interval 2 35))
(2.000000000000002 2.9999972321057697 4.000000000000006 5.0000017463386754
 6.000002917879925 6.999996178069843 8.0 9.000000167295084 10.000001863218898
 11.000001351543345 11.99999830477194 13.000002728575879 13.999996435889251
 14.999995695420948 16.0 17.00000009750988 18.000000226673244
 18.999999491923184 20.000000674351934 21.00000084963581 22.00000129055138
 23.000001745905273 23.999997516673048 25.000002359656477 26.000003200480005
 27.000003633620686 27.999996422667085 29.000004085470522 30.00000462249296
 31.000004643210133 32.00000000000583 32.999999956237566 34.00000006902297
 34.99999975385245)

35 乗根までテストしたので、たぶん合ってる。