StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy do these slightly different methods for finding roots yield different results?
text
Body
copied!<p>Consider these two slightly different methods for computing fifth roots:</p> <pre><code>(define (fifth-root-right x) (fixed-point-of-transform (lambda (y) (/ x (expt y 4))) (repeated average-damp 2) 1.0)) (define (fifth-root-wrong x) (fixed-point (repeated (average-damp (lambda (y) (/ x (expt y 4)))) 2) 1.0)) </code></pre> <p>Both attempt to compute fifth roots by an average dampened search for a fixed point, since a fifth root of x is a fixed point of the map y -> x/(y^4). I've defined</p> <pre><code>(define (average-damp f) (lambda (x) (average x (f x)))) (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 (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess)) (define (repeated f n) (if (= n 1) f (compose f (repeated f (- n 1))))) (define (compose f g) (lambda (x) (f (g x)))) </code></pre> <p>Trying both methods, we get </p> <pre><code>> (fifth-root-right 32) 2.000001512995761 > (fifth-root-wrong 32) 2.8804315666156364 </code></pre> <p>Why does the second method give fail to correctly compute fifth roots? Stranger still, if we try this wrong method on fourth or third roots, it works correctly:</p> <pre><code>(define (fourth-root x) (fixed-point (repeated (average-damp (lambda (y) (/ x (expt y 3)))) 2) 1.0)) (define (cube-root x) (fixed-point (repeated (average-damp (lambda (y) (/ x (expt y 2)))) 2) 1.0)) > (fourth-root 16) 1.982985155172348 > (cube-root 8) 2.0000009087630515 </code></pre> <p>For reference, this code attempts to solve <a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_thm_1.45" rel="nofollow">Exercise 1.45</a> in <em>Structure and Interpretation of Computer Programs</em>. Now that I have the right method, my code works, but I don't understand why my wrong method is wrong.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload