Skip to main content
edited tags
Link
200_success
  • 144.2k
  • 22
  • 188
  • 473
added 11 characters in body; edited title
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

(Scheme) Use Newton's Method to compute sqrt(x)

Given the following task:

Use Newton's method to compute the square root of a number. Newton's method involves successive approximation. You start with a guess, and then continue averaging successive guesses until you reach a satisfactory level of precision.

Use Newton's method to compute the square root of a number. Newton's method involves successive approximation. You start with a guess, and then continue averaging successive guesses until you reach a satisfactory level of precision.

I wrote the following (rough) solution in Scheme. Can you help me make it better?

(define (abs x) ((if (< x 0) - +)  x))
(define (almost-equal x y delta) 
    (> delta (abs (- x y))))

(define (sqrt-prime x last-x)
  (let ((next-x (/ (+ x last-x) 2)))
        (if (almost-equal next-x x 0.000001) x
            (sqrt-prime next-x x))))
  
(define (sqrt x) (sqrt-prime x 1))

(Scheme) Use Newton's Method to compute sqrt(x)

Given the following task:

Use Newton's method to compute the square root of a number. Newton's method involves successive approximation. You start with a guess, and then continue averaging successive guesses until you reach a satisfactory level of precision.

I wrote the following (rough) solution in Scheme. Can you help me make it better?

(define (abs x) ((if (< x 0) - +)  x))
(define (almost-equal x y delta) 
    (> delta (abs (- x y))))

(define (sqrt-prime x last-x)
  (let ((next-x (/ (+ x last-x) 2)))
        (if (almost-equal next-x x 0.000001) x
            (sqrt-prime next-x x))))
  
(define (sqrt x) (sqrt-prime x 1))

Use Newton's Method to compute sqrt(x)

Given the following task:

Use Newton's method to compute the square root of a number. Newton's method involves successive approximation. You start with a guess, and then continue averaging successive guesses until you reach a satisfactory level of precision.

I wrote the following (rough) solution in Scheme. Can you help me make it better?

(define (abs x) ((if (< x 0) - +)  x))
(define (almost-equal x y delta) 
    (> delta (abs (- x y))))

(define (sqrt-prime x last-x)
  (let ((next-x (/ (+ x last-x) 2)))
        (if (almost-equal next-x x 0.000001) x
            (sqrt-prime next-x x))))
  
(define (sqrt x) (sqrt-prime x 1))
Rollback to Revision 2
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237
(define (abs x) ((if (< x 0) - +)  x))
(define (almost-equal? x y delta) 
    (> delta (abs (- x y))))

(define (sqrt-prime x last-x)
  (let ((next-x (/ (+ x last-x) 2)))
        (if (almost-equal? next-x x 0.000001) x
            (sqrt-prime next-x x))))
  
(define (sqrt x) (sqrt-prime x 1))

EDIT: I realized that the code above did not work correctly, so I have revised to the following. It has gotten more verbose in the process. Can you help me simplify it?

(define (almost-equal? x y delta) 
    (> delta (abs (- x y))))
(define (square x) (* x x))
(define (better-guess guess x) (/ (+ (/ x guess) guess) 2.0))
(define (good-enough? guess x) (almost-equal? (square guess) x 0.000001))

(define (sqrt-prime guess last-guess x)
  (if (good-enough? guess x) guess
      (sqrt-prime (better-guess guess x) guess x)))
  
(define (sqrt x) (sqrt-prime x 1.0 x))

EDIT: Based on feedback received on my (cuberoot ...) question, I have updated to the following:

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

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

(define (almost-equal? x y delta) 
    (> delta (abs (- x y))))

(define (square x) (* x x))

(define (sqrt x) 
  (define (good-enough? guess) 
    (almost-equal? (square guess) x 0.000001))
  (define (better-guess guess) (mean (/ x guess) guess))
  (apply-until better-guess good-enough? x))
(define (abs x) ((if (< x 0) - +)  x))
(define (almost-equal? x y delta) 
    (> delta (abs (- x y))))

(define (sqrt-prime x last-x)
  (let ((next-x (/ (+ x last-x) 2)))
        (if (almost-equal? next-x x 0.000001) x
            (sqrt-prime next-x x))))
  
(define (sqrt x) (sqrt-prime x 1))

EDIT: I realized that the code above did not work correctly, so I have revised to the following. It has gotten more verbose in the process. Can you help me simplify it?

(define (almost-equal? x y delta) 
    (> delta (abs (- x y))))
(define (square x) (* x x))
(define (better-guess guess x) (/ (+ (/ x guess) guess) 2.0))
(define (good-enough? guess x) (almost-equal? (square guess) x 0.000001))

(define (sqrt-prime guess last-guess x)
  (if (good-enough? guess x) guess
      (sqrt-prime (better-guess guess x) guess x)))
  
(define (sqrt x) (sqrt-prime x 1.0 x))

EDIT: Based on feedback received on my (cuberoot ...) question, I have updated to the following:

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

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

(define (almost-equal? x y delta) 
    (> delta (abs (- x y))))

(define (square x) (* x x))

(define (sqrt x) 
  (define (good-enough? guess) 
    (almost-equal? (square guess) x 0.000001))
  (define (better-guess guess) (mean (/ x guess) guess))
  (apply-until better-guess good-enough? x))
(define (abs x) ((if (< x 0) - +)  x))
(define (almost-equal x y delta) 
    (> delta (abs (- x y))))

(define (sqrt-prime x last-x)
  (let ((next-x (/ (+ x last-x) 2)))
        (if (almost-equal next-x x 0.000001) x
            (sqrt-prime next-x x))))
  
(define (sqrt x) (sqrt-prime x 1))
added 599 characters in body
Source Link
jaresty
  • 2.2k
  • 1
  • 25
  • 45
Loading
added 637 characters in body
Source Link
jaresty
  • 2.2k
  • 1
  • 25
  • 45
Loading
added 2 characters in body
Source Link
jaresty
  • 2.2k
  • 1
  • 25
  • 45
Loading
edited tags
Link
Inaimathi
  • 2.2k
  • 12
  • 24
Loading
Source Link
jaresty
  • 2.2k
  • 1
  • 25
  • 45
Loading