Square root approximation

Square-root of x can be defined as

x^1/2 = y such that y >= 0 and y^2 = x

This describes a mathematical function. We could use it to recognise whether one number is the square root of another but it didn’t tells us anything about how to actually find the square root of a given number.

Square roots by Newton’s method

The most common way is to use Newton’s method of successive approximations, which says that whenever we have a guess ‘y’ for the value of the square root of a number ‘x’, we can perform a simple manipulation to get a better guess (one closer to the actual square root) by averaging ‘y’ with ‘x/y’

Lets try to calculate the square roots of 2, start with guess value as 1.

+--------+--------------------+--------------------------------+
| Guess  |      Quotient      |            Average             |
+--------+--------------------+--------------------------------+
|      1 | (2/1) = 2          | ((2 + 1)/2) = 1.5              |
|    1.5 | (2/1.5) = 1.3333   | ((1.3333 + 1.5)/2) = 1.4167    |
| 1.4167 | 2/1.4167) = 1.4118 | ((1.4167 + 1.4118)/2) = 1.4142 |
| 1.4142 | ....               | ....                           |
+--------+--------------------+--------------------------------+

Scheme procedure

;; Convert Above square root definition in procedure.
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x)
               x)))
;; Define good-enough? and improve procedures.
;; We call guess is good-enough if the absolute difference
;; in square-of-guess and actual number is less than 0.001.
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
  
(define (improve guess x)
  (average guess (/ x guess))
;; Define square and average procedures.
(define (square x) (* x x))

(define (average x y) (/ (+ x y) 2))
;; Start the approximation by assuming initial guess value is 1.
(define (sqrt x)
  (sqrt-iter 1.0 x))
;; TEST
;; 1 ]=> (sqrt 2)

;; ;Value: 1.4142156862745097

NOTE: The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess

;; alternate approach to check guess value
(define (good-enough? guess x)  
  (< (abs (- (improve guess x) guess)) (* guess 0.001)))