SICP-2nd-Edition-Exercise-1.16
From Boozled
Contents |
Exercise 1.16 From SICP
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
, 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 a * bn 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.)
Attempt
If our state variable starts with a = 1 then our first iteration has:
1 * bn = a * bn = bn
So bn must be maintained through the procedure.
The clue they give us is
The method used by the authors is that when they halved n they would then square the result returned from (fast-iter). Our method will square b then halve n and pass this to (my-fast-iter).
Scheme
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
; I use the "fast-expt" from the book to display a*b^n as the procedure is run(define (square x) (* x x))
(define (my-fast-expt a b n)
(cond ((= n 0)
a)((even? n)
(display (* a (fast-expt b n))) (newline)
(my-fast-expt a (square b) (/ n 2)) )
(else
(display (* a (fast-expt b n))) (newline)
(my-fast-expt (* a b) b (- n 1)))))
(define base 3)
(define power 2)
(define state 1)
(display (my-fast-expt state base power))
Parent Course
6.001_Structure_and_Interpretation_of_Computer_Programs
