schemeracketsicp

SICP Exercise 1.8 - Why doesn't my function terminate?


I'm trying to implement Newton's method for cube roots, but my function seems to hang. My code is almost identical to the code the book shows for the square root, with the improve function modified as appropriate.

Here is my code...

(define (cube-root x)
  (cube-root-iter 1.0 x))

(define (cube-root-iter guess x)
  (if (good-enough? guess x)
      guess
      (cube-root-iter (improve x guess) x)
      )
  )

(define (good-enough? guess x)
  (< (abs (- (* guess guess) x)) 0.001))

(define (improve x guess)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3)
  )

I tested improve and good-enough? independently, and they seem to give the right answers. Anyone know why my code doesn't terminate?

I'm doing this in Racket with the sicp package in case that makes any difference.


Solution

  • You want to compute the cube root. The cube root of x means a value y for which y*y*y = x, by definition. You try to approximate y using guess, but you compute only y^2. Need to multiply it 3 times:

    (define (good-enough? guess x)
      (< (abs (- (* guess guess guess) x))
         0.001))
    

    If you multiply it only 2 times, y^2 will never get close enough to y^3, which gets closer to x. If you try to compute cube root of 1 or of 0 with your code it might work however (and only for these inputs it might work).