SICP Exercise 1.3 – Sum of Squares

The exercise asks us to write a procedure which returns the sum of the squares of the two larger numbers given three numbers.

First, we setup the square procedure.

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

and using this, write a procedure to return the sum of the squares of two given numbers.

(define (sum-squares x y) (+ (square x) (square y)))

Now, we need to write the procedure. Given three numbers, x, y and z, there are three possibilities:

  • (and (< x y) (< x z)), which means that x is the smallest of the three numbers, so we need to return the sum of the squares of y and z.
  • (and (< y x) (< y z)), which means that y is the smallest and we need to return the sum of the squares of x and z.
  • (and (< z x) (< z x)), which means that z is the smallest and we need to return the sum of the squares of x and y. If we check for the first two conditions, we don’t need to explicitly state the third one, since if either x or y is not the smallest, then z is the smallest one.

So, the procedure can now be written as:

(define (sum-squares-largest x y z)
    (cond ((and (< x y) (< x z)) (sum-squares y z))
          ((and (< y x) (< y z)) (sum-squares x z))
          (else (sum-squares x y))))

The given procedure can also be written without cond expressions by using the built-in procedures min and max.

Suppose we take the pair (y, z), then at least one variable out of this pair is in the maximum two and it is indeed the maximum of these 2 variables, i.e. (max y z). Now, to find if the other variable, i.e. (min y z) is in the maximum two, we can take the maximum of that with x, thus giving us the procedure

(define (sum-square-largest x y z)
    (sum-squares (max y z) (max x (min y z))))

Another clever way to do this question is by using rotations, as specified in the blog ProgrammingPraxis.

The idea is to recursively call the same procedure until the first argument is the minimum of the three, and this is done by rotating the arguments at every call until the minimum is at the first position.

(define (sum-square-largest x y z)
    (if (= x (min x y z)) (sum-squares y z)
        (sum-square-largest y z x)))

The above procedure works by finding out the minimum of the three variables using the min procedure, and comparing it with the first argument, if they are found equal, the sum of squares of the other two arguments is calculated, else, the arguments are rotated and the procedure is recursively called. The procedure can be called a maximum of 3 times (including the first call).

About these ads

One thought on “SICP Exercise 1.3 – Sum of Squares

  1. Random Human says:

    Make getting the largest two out of three a separate procedure – it will make the final definition clearer.
    Also, the largest two can be found in at most 2 comparisons.

    Sample:

    (define (sum-squares-largest a b c)
      (let* ((max-2 (lambda (a b c)
                      (if (> a b)
                        (if (> b c) `(,a ,b) `(,a ,c))
                        (if (> a c) `(,a ,b) `(,b ,c)))))
             (square (lambda (a) (* a a)))
             (sum-squares (lambda (a b) (+ (square a) (square b)))))
        (apply sum-squares (max-2 a b c))))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s