Cube root (Newton's method)

Question

Newton's method for finding cube roots states that for any given \$x\$ and a guess \$y\$, a better approximation is \$\dfrac{(\dfrac{x}{y^2} + 2y)}{3}\$.

What do you think of this code for finding a cube root in Scheme?

(define (improveguess y x)
  ; y is a guess for cuberoot(x)
  (/ (+ (/ x (expt y 2)) (* 2 y)) 3))

(define (cube x) (* x x x))

(define (goodenough? guess x)
  (< (/ (abs (- (cube guess) x)) guess) 0.0001))

(define (cuberoot x) (cuberoot-iter 1.0 x))

(define (cuberoot-iter guess x) 
  (if (goodenough? guess x) guess
      (cuberoot-iter (improveguess guess x) x)))

Answer 1

If you look at your code for this exercise as well as the one about approximating the square root and the one about finding epsi, you'll notice a common pattern:

You have a function which performs a single step and a predicate which tells you when you're done. You then apply the stepping function until the predicate is met. When you encounter a common pattern like this, the best thing to do is usually to abstract it. So let's define an apply-until function which takes a stepping function, a predicate and an initial value and applies the function to the value until the predicate is met:

(define (apply-until step done? x)
  (if (done? x) x
      (apply-until (step x) step done?)))

You can now define your cuberoot function using apply-until instead of cuberoot-iter:

(define (cuberoot x)
  (apply-until (lambda (y) (improve-guess y x)) (lambda (guess) (goodenough? guess)) 1.0))

You can also move your helper functions as local functions into the cuberoot function. This way they don't need to take x as an argument (as they will close over it) and can thus be passed directly to apply-until without using lambda:

(define (cuberoot x)
  (define (improveguess y)
    ; y is a guess for cuberoot(x)
    (/ (+ (/ x (expt y 2)) (* 2 y)) 3))

  (define (goodenough? guess)
    (< (/ (abs (- (cube guess) x)) guess) 0.0001))

  (apply-until improveguess goodenough? 1.0))

Answer 2

Your improve-guess is probably better written like this:

(/ (+ (/ x y y) y y) 3)

Or, if you define a mean function:

(define (mean . xs)
  (/ (apply + xs) (length xs)))

then you can make improve-guess even simpler:

(mean (/ x y y) y y)