58 lines
1.1 KiB
Scheme
58 lines
1.1 KiB
Scheme
(load "1_43.sch") ; for repeated
|
|
|
|
;; Fixed points
|
|
|
|
(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) (average x (f x))))
|
|
|
|
(define (average x y)
|
|
(/ (+ x y) 2))
|
|
|
|
(define (sqrt x)
|
|
(fixed-point (average-damp (lambda (y) (/ x y)))
|
|
1.0))
|
|
|
|
(define (cube-root x)
|
|
(fixed-point (average-damp (lambda (y) (/ x (square y))))
|
|
1.0))
|
|
|
|
(define (cubed x) (* x x x))
|
|
|
|
(define (pow x n)
|
|
(define (iter i res)
|
|
(if (= i 0)
|
|
res
|
|
(iter (- i 1) (* x res))))
|
|
(iter n 1))
|
|
|
|
(define (fourth-root x)
|
|
(fixed-point ((repeated average-damp 2)
|
|
(lambda (y) (/ x (cubed y)))) 1.0))
|
|
|
|
; n-th root calculation via fixed-point requires log_2(n)
|
|
; applications of average damp
|
|
(define (required-damps n)
|
|
(floor (/ (log n) (log 2))))
|
|
|
|
(define (root x n)
|
|
(fixed-point ((repeated average-damp (required-damps n))
|
|
(lambda (y) (/ x (pow y (- n 1))))) 1.0))
|
|
|
|
; 6 2
|
|
; 8 3
|
|
; 16 4
|