#lang racket
;;;;;;;;;;
;; 1.40 ;;
;;;;;;;;;;
(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 dx 0.00001)
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
(define (cubic a b c)
(lambda (x)
(+ (* x x x)
(* a x x)
(* b x)
c)))
(newtons-method (cubic 0 0 -8) 1.0)
;; 2.000000000036784
(newtons-method (cubic 1 1 1) 1.0)
;; -0.9999999999997796
;;;;;;;;;;
;; 1.41 ;;
;;;;;;;;;;
(define (double f)
(lambda (x) (f (f x))))
(((double (double double)) add1) 5)
;; 21
;;;;;;;;;;
;; 1.42 ;;
;;;;;;;;;;
(define (my-compose f g)
(lambda (x) (f (g x))))
((my-compose sqr add1) 6)
;; 49
;;;;;;;;;;
;; 1.43 ;;
;;;;;;;;;;
(define (repeated f n)
(if (= n 1)
f
(my-compose f (repeated f (sub1 n)))))
((repeated sqr 2) 5)
;; 625
;;;;;;;;;;
;; 1.44 ;;
;;;;;;;;;;
(define (smooth f)
(lambda (x)
(/ (+ (f (- x dx))
(f x)
(f (+ x dx)))
3)))
(define (n-fold-smooth f n)
((repeated smooth n) f))
(for ([i (in-range 1 6)])
(displayln (log i)))
;; 0
;; 0.6931471805599453
;; 1.0986122886681098
;; 1.3862943611198906
;; 1.6094379124341003
(for ([i (in-range 1 6)])
(displayln (((repeated smooth 10) log) i)))
;; -3.333332199762096e-010
;; 0.693147180476612
;; 1.0986122886310727
;; 1.386294361099058
;; 1.6094379124207672
;;;;;;;;;;
;; 1.45 ;;
;;;;;;;;;;
(define (average a b)
(/ (+ a b)
2))
(define (average-damp f)
(lambda (x) (average x (f x))))
(define (get-damped-root power times)
(lambda (x)
; find the power-th root of x using fixed-point
; and damping the indicated number of times
(fixed-point
((repeated average-damp times) (lambda (y) (/ x (expt y (sub1 power)))))
1.0)))
(define (investigate power min-times)
(for ([times (in-range min-times (add1 power))])
(printf "power is ~a, times is ~a, answer is ~a ~n"
power
times
((get-damped-root power times) (expt 2 power)))))
;; I used the investigate function to find all powers and times,
;; for powers = 2, 3, ..., 17, and times = 1, 2, ..., power,
;; that did not converge.
;; did not converge
;; power times-damped
;; 4 1
;; 5 1
;; 8 2
;; 9 2
;; 10 2
;; 11 2
;; 13 1
;; 13 2
;; 14 2
;; 16 3
;; 17 2
;; 17 3
;; I don't see any obvious pattern here. The sample is too small. But damping
;; four times should work for most small powers.
(define (my-root n)
(get-damped-root n 4))
(for ([n (in-range 2 20)])
(displayln ((my-root n) (expt 2 n))))
;; 1.9999378937004895
;; 1.9999583385968283
;; 1.9999751575244828
;; 2.0000200551235574
;; 2.000011071925238
;; 2.0000106805408264
;; 2.000008820504543
;; 2.0000074709755573
;; 2.0000044972691784
;; 2.0000038760178884
;; 2.000001241323132
;; 2.000001923509733
;; 2.0000006317785997
;; 2.0000001141598975
;; 2.000000000076957
;; 2.0000000561635765
;; 2.0000005848426476
;; 2.0000003649180282
;;;;;;;;;;
;; 1.46 ;;
;;;;;;;;;;
(define (iterative-improve good-enough? improve-guess)
(define (iterate guess)
(if (good-enough? guess)
guess
(iterate (improve-guess guess))))
iterate)
(define (new-sqrt x)
(define (good-enough? guess)
(< (abs (- (sqr guess) x)) 0.001))
(define (improve-guess guess)
(average guess (/ x guess)))
((iterative-improve good-enough? improve-guess) 1.0))
(for ([i (in-range 2 10)])
(displayln (new-sqrt i)))
;; 1.4142156862745097
;; 1.7321428571428572
;; 2.0000000929222947
;; 2.2360688956433634
;; 2.4494943716069653
;; 2.64576704419029
;; 2.8284685718801468
;; 3.00009155413138
(define (new-fixed-point f first-guess)
(define (good-enough? guess)
(< (abs (- guess (f guess))) 0.00001))
((iterative-improve good-enough? f) first-guess))
;; solve x ^ x = 1000 by finding the fixed point of f(x) = log(1000) / log(x)
(define soln (new-fixed-point (lambda (x) (/ (log 1000) (log x)))
2.0))
soln
;; 4.555540912917957
(expt soln soln)
;; 1000.0131045064136
Comments