Solutions: If evaluation and square roots by Newton’s Method:

Exercise 1.6

Alyssa P. Hacker decides to make a new version of if in terms of cond as a procedure. The new-if seems to work for basic cases as shown by Eva, and Alyssa decides to rewrite the square-root program with new-if

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
  (else else-clause)))

Here is the square root procedure:

;; SICP - Second Edition
;; Chapter 1
;; Author- Dedipyaman Das (2d@twodee.me)
;; Square root approximation - v1

(define (avg x y)
  (/ (+ x y) 2))

;; Block structure
(define (new-sqrt x)
  (define (improve guess)
    (avg guess
	 (/ x guess)))
  (define (good-enough? guess)
    (< (abs (- x (square guess)))
       0.001))
  (define (try guess)
    (if (good-enough? guess)
	guess
	(try (improve guess))))
  (try 1))

Implementing Alyssa’s version of if, the new-if in sqrt-iter:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                      x)))

When Alyssa attempts to run it, since Scheme uses Applicative order evaluation, the interpreter will try to evaluate sqrt-iter in a never ending loop because of the nature of evaluating procedures in applicative order.

What she didn’t realize is that if is not a procedure. It is a special form which doesn’t act as a procedure underneath, and its conditions are checked first and then the clauses are implemented. Hence, new-if won’t work the way if would.

Exercise 1.7: Improving square root approximation

The new-sqrt procedure that I mentioned above doesn’t starts failing at very large numbers, the break-point I found in my computer (with some manual binary search) was: 17738094999817, trying any number larger than that would not work as intended. This test was also true for very small numbers (having too many zeroes after the decimal point).

The alternative checks for the change of guess. If the difference of the guess and the new guess is small enough, we can consider it a good-enough guess. This is the implementation:

;; SICP- Second Edition
;; Exercise 1.7
;; Author- Dedipyaman Das (2d@twodee.me)
;; Square root finder with an improved 'good-enough?'
;; Works with way greater numbers than 17738094999818 - Where it failed
;; With the older version
(define (square a)
  (* a a))
(define (avg x y)
  (/ (+ x y) 2))

(define (sqrt-2 x)
  (define (improve guess)
    (avg guess
	 (/ x guess)))
  ;; good-enough? - Watch till the change in guess is very small.
  ;; Current guess is 'guess' and the next guess will be '(improve guess)'
  (define (good-enough? guess)
    (< (abs (- guess (improve guess)))
       0.001))
  (define (try guess)
    (if (good-enough? guess)
	(improve guess)
	(try (improve guess))))
  (try 1))

This seems to work perfectly fine for very large and small numbers and it easily passes the break point. Hence, we have an improvement in our sqrt procedure.

Exercise 1.8: Cube root procedure

A rather simple exercise that asks us to implement a cube-root procedure analogous to our new sqrt procedure, this is based on Newton’s method for cube roots to approximate the values:

;; SICP- Second Edition
;; Exercise 1.8
;; Author- Dedipyaman Das (2d@twodee.me)
;; Finds the cube root using Newton's method
;; With the older version

;; This procedure is general enough to not be included in the block
  (define (square x)
    (* x x))

(define (cube-root x)
  ;; Given algorithm to find a better approximation
  (define (improve guess)
    (/ (+ (/ x (square guess)) (* 2 guess))
       3))
  ;; Based on a better approximation algorithm
  ;; Smaller deviation is guess is a good guess
  (define (good-enough? guess)
    (< (abs (- guess
	       (improve guess)))
       0.001))
  ;; Bootstrapping everything
  (define (try guess)
    (if (good-enough? guess)
	guess
	(try (improve guess))))
  (try 1))

This program works well enough to calculate cube roots. No further comments.

Dedipyaman