Exercise1-35 <---> Exercise1-37
Exercise 1.36
Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to xx = 1000 by finding a fixed point of 
. (Use Scheme's primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)
Scheme solution:
; I found it useful to write a number of current step along with current value
(define (fixed-point f first-guess)
(define (close? v1 v2) (< (abs (- v1 v2)) 0.0001))
(define (try guess step)
(let ((next (f guess)))
(display step) (display ":\t") (display guess) (newline)
(if (close? guess next) next (try next (+ step 1)))))
(try first-guess 1))
(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.) ; without average damping. Ends in 29 steps.
(fixed-point (lambda (x) (/ (+ x (/ (log 1000) (log x))) 2)) 2.) ; with damping. Ends in 8 steps.
Haskell solution:
fixed'point f start = iter start (f start)
where
iter old new = do print old
if close'enuf old new then return new
else iter new (f new)
close'enuf u v = abs (u-v) < tolerance
tolerance = 0.0001
undamped guess = fixed'point (\x -> logBase x 1000) guess
damped guess = fixed'point (\x -> average x (logBase x 1000)) guess
where average a b = (a+b)/2
OCaml solution:
let fixed_point f start =
let tolerance = 0.0001 in
let close_enuf u v = abs_float (u -. v) < tolerance in
let rec iter old nu = (* "new" is a reserved keyword in OCaml *)
Printf.printf "%f\n" old;
if close_enuf old nu then
nu
else
iter nu (f nu)
in
iter start (f start)
let undamped guess = fixed_point (fun x -> log 1000. /. log x) guess
let damped guess =
let average a b = (a +. b) /. 2. in
fixed_point (fun x -> average x (log 1000. /. log x)) guess
Standard ML solution:
fun fixed_point (f, start) = let
val tolerance = 0.0001
fun close_enuf (u, v) = abs (u - v) < tolerance
fun iter (old, new) = (
print (Real.toString old ^ "\n");
if close_enuf (old, new) then
new
else
iter (new, f new)
)
in
iter (start, f start)
end
fun undamped guess = fixed_point (fn x => Math.ln 1000.0 / Math.ln x, guess)
fun damped guess = let
fun average (a, b) = (a + b) / 2.0
in
fixed_point (fn x => average (x, Math.ln 1000.0 / Math.ln x), guess)
end
Exercise1-35 <---> Exercise1-37
Comments
| (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0) Assuming tolerance 0.00001 took 35 steps to give result as 4.555532270803653 (fixed-point (lambda (x) (/ (+ (/ (log 1000) (log x)) x) 2)) 2.0) Assuming same tolerance took 10 steps to give 4.555537551999825 | ||||
| Posted by SriramDevadas at 2009-04-13 01:53:06 | ||||