SICP. 1.2.4
2022-12-27 Tue

The authors present a procedure that evolves a linear recursive process to compute the exponential of a given number (here translated in Emacs Lisp):

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

This requires \(\Theta(n)\) steps and \(\Theta(n)\) space.

We have have already seen such a kind of process (linear recursion) with factorial. Just as they have done with factorial, the authors present a procedure that evolves a linear iterative process to compute the exponentional of a given number:

(defun expt-iter (b counter product)
  (if (= counter 0)
      product
    (expt-iter b
               (- counter 1)
               (* b product))))

This process requires \(\Theta(n)\) steps and \(\Theta(1)\) space.

Then, the authors show that we can be faster:

(defun fast-expt (b n)
  (cond ((= n 0)
         1)
        ((evenp n)
         (square (fast-expt b (/ n 2))))
        (t
         (* b (fast-expt b (- n 1))))))

(defun (evenp n)
    (= (% n 2) 0))

fast-expt evolves a process that grows logarithmically with n in both space and time.

Exercise 1.16

Exercise:

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 \((b^{b/2})^2 = (b^2)^{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.)

Answer:

(defun fast-expt-i (b n)
  (fast-expt-iter b n 1))

(defun fast-expt-iter (b n a)
  (cond ((= n 0) a)
        ((even n)
         (fast-expt-iter (square b) (/ n 2) a))
        (t
         (fast-expt-iter b (- n 1) (* b a)))))

Exercise 1.17

Exercise:

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.

Answer:

(defun double (a)
  (* a 2))

(defun halve (a)
  (/ a 2))

(defun fast-* (a b)
  (cond ((= b 1) a)
        ((even b) (double (fast-* a (halve b))))
        (t (+ a (fast-* a (- b 1))))))

Exercise 1.18

Exercise:

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 (fn: This algorithm, which is sometimes known as the “Russian peasant method” of multiplication, is ancient. Examples of its use are found in the Rhind Papyrus, one of the two oldest mathematical documents in existence, written about 1700 B.C. (and copied from an even older document) by an Egyptian scribe named A’h-mose.)

Answer:

(defun fast-*-i (a b)
  (fast-*-iter a b 0))

(defun fast-*-iter (a b c)
  (cond ((= c 0) 0)
        ((even b) (fast-*-iter (double a) (halve b) c))
        (t (fast-*-iter a (- b 1) (+ a c))

←

SICP. 1.2.4 2022-12-27 Tue

Exercise 1.16

Exercise 1.17

Exercise 1.18

SICP. 1.2.4
2022-12-27 Tue