Laboratory Problem 4
Exponentiation
In this problem we study algorithms for evaluating bn where b is any real number and n is a positive integer exponent. One way to do this is via the recursive definition
(expt b n) = (* b (expt b (- n 1)))
where
(expt b 0) = 1
We might be tempted to define the following procedure:
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
We say that this is a linear recursive process, with time and space requirements O(n). By this we mean that if we try to estimate the amount of space or time taken by this algorithm we find, for example when counting multiply operations, that there is some constant, K, such that the number of multiplications is <= K x n. We pronounce this as "the number of multiplications is of order n" or "the number of multiplications is big oh of n."
Introduce some tracing functions for expt which will demonstrate that both the number of multiplications and space required by expt is of O(n).
Next consider the following procedure:
(define (expt b n)
(define (exp-iter b counter product)
(if (= counter 0)
product
(exp-iter b
(- counter 1)
(* b product))))
(exp-iter b n 1))
Introduce some tracing functions for this version of expt which will demonstrate that this version requires O(n) multiplications and O(1) space.
We can compute exponentials in fewer steps by using the idea of successive squaring. For instance, rather than computing (expt b 8) as
b x b x b x b x b x b x b x b
we can compute it using but three multiplications:
(expt b 2) = (* b b) (expt b 4) = (expt (expt b 2) 2) (expt b 8) = (expt (expt b 4) 2)
This method is, of course, limited to exponents which are even. We can extend this idea to handle any positive integer n by using the rule:
(expt b n) = (expt (expt b (/ n 2)) 2) if n is even (expt b n) = (* n (expt b (- n 1))) if n is odd
Define a faster power procedure which uses this idea. Introduce tracing functions which will help you discover the order of the number of multiplications and the order of the space required by this function.