*"Life is all about sharing. If we are good at something, pass it on." - Mary Berry*

### 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 (b^{n/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 ab^{n}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.)

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.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
- SICP Exercise 2.27: Reversing nested lists