6
\$\begingroup\$

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)))
|improve this question
\$\endgroup\$
5
\$\begingroup\$

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))
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ 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))))) \$\endgroup\$ – Chris Jester-Young Mar 24 '11 at 0:55
  • 1
    \$\begingroup\$ Is there a reason to use "let" rather than a nested "define," Chris? \$\endgroup\$ – jaresty Mar 24 '11 at 4:26
  • \$\begingroup\$ I mean, I guess I don't understand the syntax of (let ...) in scheme - what does (let loop ...) do? \$\endgroup\$ – jaresty Mar 24 '11 at 7:14
  • \$\begingroup\$ I found the answer to my question at people.csail.mit.edu/jaffer/r5rs_6.html#SEC36 under the heading "4.2.4 Iteration" \$\endgroup\$ – jaresty Mar 25 '11 at 0:10
4
\$\begingroup\$

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)
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ What does the '.' in '(define (mean . xs)' do? \$\endgroup\$ – jaresty Mar 23 '11 at 13:30
  • 1
    \$\begingroup\$ @jaresty - that's the scheme notation for a &rest argument. \$\endgroup\$ – Inaimathi Mar 23 '11 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.