n乗根の計算で、平均緩和を何回かしないと収束しないことがあるらしい。
こんなの作ってしらべた。
(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))) (display guess) (newline) (if (close-enough? guess next) next (try next)))) (try first-guess)) (define (average-damp f) (lambda (x) (/ (+ x (f x)) 2))) (define (compose f g) (lambda (x) (f (g x)))) (define (repeated f n) (define (sub-repeated n) (if (= n 0) f (compose f (sub-repeated (- n 1))))) (lambda (x) ((sub-repeated (- n 1)) x))) (define (n-average-damping-root n m x first-guess) (fixed-point ((repeated average-damp m) (lambda (y) (/ x (expt y (- n 1))))) first-guess))
これで、n-average-damping-rootに対して、xをに、first-guessを1.0にしたときの結果がこちら。
n | 収束するための平均緩和必要回数 |
---|---|
3 | 1 |
4 | 2 |
5 | 2 |
6 | 2 |
7 | 2 |
8 | 3 |
9 | 3 |
10 | 3 |
11 | 3 |
12 | 3 |
13 | 3 |
14 | 3 |
15 | 3 |
16 | 4 |
どうも、でいけるぽい。
つーわけで、ホントのn乗根を求める関数。
(define (n-root n x first-guess) (let ((m (floor (sqrt n)))) (fixed-point ((repeated average-damp m) (lambda (y) (/ x (expt y (- n 1))))) first-guess)))
収束するまで遅いので、初期値(first-guess)に3を渡した。
gosh> (n-root 16 65536 3.0) 3.0 2.812785457282565 2.6377367973089667 2.4748456266926095 2.3252862223193755 2.1929939143600716 2.0873223176370694 2.0227088232732235 2.0018155067539998 2.0000122969214313 2.0000000005670335 2.0