# Cube root (Newton's method)

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)))


## 2 Answers

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))

• To hoist the constant "variables" in apply-until so that you don't have to pass them in over and over, I'd implement using a named let: (define (apply-until done? next x) (let loop ((x x)) (if (done? x) x (loop (next x))))) Mar 24, 2011 at 0:55
• Is there a reason to use "let" rather than a nested "define," Chris? Mar 24, 2011 at 4:26
• I mean, I guess I don't understand the syntax of (let ...) in scheme - what does (let loop ...) do? Mar 24, 2011 at 7:14
• I found the answer to my question at people.csail.mit.edu/jaffer/r5rs_6.html#SEC36 under the heading "4.2.4 Iteration" Mar 25, 2011 at 0:10

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)

• What does the '.' in '(define (mean . xs)' do? Mar 23, 2011 at 13:30
• @jaresty - that's the scheme notation for a &rest argument. Mar 23, 2011 at 18:08