SICP Exercise 1.16: Iterative Exponentiation

Quan Tong

"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.

Exercise 1.16:

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)² = (b²)^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ⁿ 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)²
(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:

Tags: sicp scheme recursion tail-recursion iteration

Edit on GitHub