2015/10/09

SICP 問題1.45

;;実験用に作った手続き
;; x^n k回平均緩和
(define (test x n k)
  (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
                            (lambda (z) ((repeated average-damp k) z))
                            1.0))

実験の結果,
2 ≦ n < 4 の時 k=1
4 ≦ n < 8 の時 k=2
8 ≦ n < 16 の時 k=3
16 ≦ n < 32 の時 k=4
32 ≦ n < 64 の時 k=5
n乗根に必要な平均緩和の回数は(log2 n) 回(小数部分切り捨て).
n√xを求めるnth-rootを実装する.

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

© 2022 wat-aro