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

Section 1.2.4 talks about the problem of computing the exponential of a given number.

```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 exponent `n` and the base `b`, an additional state variable `a`, and define the state transformation in such a way that the product abn 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:

Tags:

Related Posts: