Vincent Costel

SICP exercises 1.16 to 1.18

These exercises are part of chapter 1.2.4 Exponentiation.

Exercise 1.16 #

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (bn/2)2) = (b2)n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product abn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Earlier in the chapter, we are given a recursive procedure fast-expt for computing exponentials of a given number.
It is "fast" because it uses successive squaring to reduce the number of steps to Θ(log n).

  (define (fast-expt b n)
    (define (square x)
      (* x x))
    (cond ((= n 0) 
          1)
          ((even? n) 
          (square (fast-expt b (/ n 2))))
          (else 
          (* b (fast-expt b (- n 1))))))

The goal of the exercise is to create an iterative algorithm for fast exponentiation.

  ; Exercise 1.16
  ; Iterative implementation

  (define (fast-expt b n)
    (define (square x)
      (* x x))
    (define (iter b n a)
      (cond ((= n 0)
            a)
            ((even? n) 
            (iter (square b) (/ n 2) a))
            (else
            (iter b (- n 1) (* a b)))))
    (iter b n 1))

  ; Testing
  (fast-expt 2 16)
  (fast-expt 2 15)
  (fast-expt 2 14)
  (fast-expt 2 13)
  (fast-expt 2 12)
  (fast-expt 2 11)
  (fast-expt 2 10)
  (fast-expt 2 9)
  (fast-expt 2 8)
  (fast-expt 2 7)
  (fast-expt 2 6)
  (fast-expt 2 5)
  (fast-expt 2 4)
  (fast-expt 2 3)
  (fast-expt 2 2)
  (fast-expt 2 1)

The test outputs the powers of 2 from 216 to 21. Negative values of n are not supported and will send the program into an infinite loop.

  65536
  32768
  16384
  8192
  4096
  2048
  1024
  512
  256
  128
  64
  32
  16
  8
  4
  2

Exercise 1.17 #

The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure: 
(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))
This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

The above multiplication procedure is very similar to the linear recursive procedure expt for exponentiation given at the start of the chapter:

  (define (expt b n)
    (if (= n 0) 
        1 
        (* b (expt b (- n 1)))))

Using the same process used to reformulate expt into fast-expt, we can create the fast-mult procedure:

  ; Exercise 1.17
  ; Recursive implementation

  (define (fast-mult a b)
    (define (double x)
      (+ x x))
    (define (halve x)
      (/ x 2))
    (cond ((= b 0)
          0)
          ((even? b)
          (double (fast-mult a (halve b))))
          (else
          (+ a (fast-mult a (- b 1))))))
          
  ; Testing
  (fast-mult 33 999) ; outputs 32967

Exercise 1.18 #

Using the results of Exercise 1.16 and Exercise 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

Using the solution to exercise 1.16, it is straightforward to figure out an iterative algorithm for the fast-mult procedure:

  ; Exercise 1.18
  ; Iterative implementation

  (define (fast-mult a b)
    (define (double x)
      (+ x x))
    (define (halve x)
      (/ x 2))
    (define (iter a b n)
      (cond ((= b 0)
            n)
            ((even? b)
            (iter (double a) (halve b) n))
            (else
            (iter a (- b 1) (+ a n)))))
    (iter a b 0))

  (fast-mult 33 999) ; outputs 32967