The following procedure generates a linear recursive process for computing \(b^n\):
(define (expt-rec b n)
(if (= n 0)
1
(* b (expt-rec b (- n 1)))))
This is just a direct translation of the following definition of exponentiation into Scheme:
\[\begin{align*} &b^n = b * b^{n-1} \\ &b^0 = 1 \end{align*}\]The above procedure uses \(O(n)\) steps and \(O(n)\) space. Here is an iterative procedure that uses \(O(1)\) space:
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))
We can compute exponents in fewer steps by taking advantage of the following fact about exponentiation:
\[b^n = (b^{n/2})^2\ \text{if n is even}\]For example, \(2^6 = (2^3)^2 = 8^2 = 64\).
Combining this successive squaring method with the original recursive method, we get the following recursive procedure:
(define (even? n)
(= (remainder n 2) 0))
(define (square n)
(* n n))
(define (fast-expt-rec b n)
(cond ((= n 0)
1)
((even? n)
(square (fast-expt-rec b (/ n 2))))
(else
(* b (fast-expt-rec b (- n 1))))))
The above procedure grows logarithmically with n (\(O(log (n))\)) in both space and time.
The following procedure generates an iterative process which uses constant space (\(O(1)\)) along with the technique for fast exponentiation described above:
(define (fast-expt b n)
(fast-expt-iter 1 b n))
(define (fast-expt-iter a b n)
(cond (( = n 0)
a)
((even? n)
(fast-expt-iter a (square b) (/ n 2)))
(else
(fast-expt-iter (* a b) b (- n 1)))))
We can prove the correctness of the above procedure by noting that the quantity \(ab^n\) is invariant in both recursive cases:
If \(n\) is even, then in the next iteration, let \(a'=a, b'=b^2, n=n/2\). Then:
\[\begin{align*} a'b'^{n'} &= (ab^2)^{n/2} \\ &= ab^n \ \text{by the identity}\ (b^m)^n = b^{mn} \end{align*}\]If \(n\) is odd, then for \(a'=ab, b'=b, n'=n-1\):
\[\begin{align*} a'b'^{n'} &= (ab)b^{n-1} \\ &= a(b^1 * b^{n-1}) \\ &= ab^n \ \text{by the identity}\ b^m * b^n = b^{m+n} \end{align*}\]