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

• C. K. Young: 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)))))
• jaresty: Is there a reason to use "let" rather than a nested "define," Chris?
• jaresty: I mean, I guess I don't understand the syntax of (let ...) in scheme - what does (let loop ...) do?
• jaresty: I found the answer to my question at people.csail.mit.edu/jaffer/r5rs_6.html#SEC36 under the heading "4.2.4 Iteration"

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)

• jaresty: What does the '.' in '(define (mean . xs)' do?
• Inaimathi: @jaresty - that's the scheme notation for a &rest argument.