SICP Exercise 1.16: Iterative Exponentiation
2021-09-29
Categories: Programming
I am reading SICP.
Section 1.2.4 talks about the problem of computing the exponential of a given number.
The authors start with a recursive procedure:
1#lang sicp 2 3(define (expt b n) 4 (if (= n 0) 5 1 6 (* b (expt b (- n 1)))))
This requires O(n) steps and O(n) space.
then an iterative procedure:
1#lang sicp 2 3(define (expt b n) 4 (expt-iter b n 1)) 5 6(define (expt-iter b counter product) 7 (if (= counter 0) 8 product 9 (expt-iter b 10 (- counter 1) 11 (* b product))))
This version requires O(n) steps and O(1) space.
and finally he suggests a procedure which requires fewer steps by using successive squaring:
1#lang sicp 2 3(define (fast-expt b n) 4 (cond ((= n 0) 1) 5 ((even? n) (square (fast-expt b (/ n 2)))) 6 (else (* b (fast-expt b (- n 1))))))
This only requires O(log n) steps.
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 exponentn
and the baseb
, an additional state variablea
, and define the state transformation in such a way that the product abn is unchanged from state to state. At the beginning of the processa
is taken to be 1, and the answer is given by the value ofa
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.)
Here’s my solution:
1#lang sicp 2 3(define (fast-expt b n) 4 (fast-expt-iter b n 1)) 5 6(define (fast-expt-iter b counter product) 7 (cond ((= counter 0) 8 product) 9 ((even? counter) 10 (fast-expt-iter (square b) 11 (/ counter 2) 12 product)) 13 (else 14 (fast-expt-iter b 15 (- counter 1) 16 (* b product)))))
Let’s see what is the difference between recursive and iterative version?
Enable debugging and run the recursive version:
1$ racket 1.16-fast-expt-recursive.scm 2>(fast-expt 2 10) 3> (fast-expt 2 5) 4> >(fast-expt 2 4) 5> > (fast-expt 2 2) 6> > >(fast-expt 2 1) 7> > > (fast-expt 2 0) 8< < < 1 9< < <2 10< < 4 11< <16 12< 32 13<1024 141024
then the iterative version:
1$ racket 1.16-fast-expt-iterative.scm 2>(fast-expt 2 10) 3>(fast-expt-iter 2 10 1) 4>(fast-expt-iter 4 5 1) 5>(fast-expt-iter 4 4 4) 6>(fast-expt-iter 16 2 4) 7>(fast-expt-iter 256 1 4) 8>(fast-expt-iter 256 0 1024) 9<1024 101024
The first thing you can easily spot is the recursive version requires more space.
The reason is after calling fast-expt
recursively, Scheme must remember to either square or multiply the result with b
depends on n
is even or odd:
- (fast-expt 2 10) = (fast-expt 2 5)2
- (fast-expt 2 5) = (fast-expt 2 4) * 2
- …
In the iterative version, Scheme doesn’t have to remember anything: after it is done, it just returns the product
.
Moreover, the iterative version also saves time:
1$ time racket 1.16-fast-expt-recursive.scm 2 3________________________________________________________ 4Executed in 540.91 millis fish external 5 usr time 407.01 millis 0.25 millis 406.77 millis 6 sys time 119.54 millis 1.84 millis 117.70 millis
1$ time racket 1.16-fast-expt-iterative.scm 2 3________________________________________________________ 4Executed in 518.87 millis fish external 5 usr time 389.04 millis 0.12 millis 388.92 millis 6 sys time 116.15 millis 1.09 millis 115.06 millis
References:
- http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html
- https://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
Tags: sicp scheme recursion tail-recursion iteration
Related Posts:
- SICP Exercise 2.77: expected a procedure that can be applied to arguments, given #f
- SICP Exercise 2.43: Eight queens: interchange the order of the nested mappings
- SICP Exercise 2.42: Eight queens puzzle
- SICP Exercise 2.41: Triple sum
- SICP Exercise 2.35: Counting leaves of a tree