Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement