## Exponentiation

Examining the difference between θ(n) and θ(log(n)) growth with successive squaring.

#### Exercise 1.16

Design an iterative exponentiation process using successive squaring
like `fast-exp`

.

The book gives a lot of clues for this exercise. Despite this, I’m too thick and it took me a long while to produce a working solution. Once I did I felt great!

Gathering up the clues:

- return the state variable at the end of the process
- a(b
^{n}) never changes from step to step - (b
^{2})^{n/2}- square of b raised to n/2 - the state variable starts at 1
- b
^{n}= b * b^{n-1} - b
^{0}= 1

Using these, I came up with:

```
(define (fast-exp b n)
(define (even? x)
(= (remainder x 2) 0))
(define (square x) (* x x))
(define (fast-exp-iter b n a)
(cond ((= n 0) a)
((even? n) (fast-exp-iter (square b) (/ n 2) a))
(else (fast-exp-iter b (- n 1) (* a b)))))
(fast-exp-iter b n 1))
```

Most of this is just setup for the `fast-exp-iter`

procedure. The result
is the accumulator variable `a`

, if the exponent is even then
b^{n} = (b^{2})^{n/2}, if the exponent is odd
then b^{n} = b * b^{n-1}. Here are some of the steps
showing how this iterative process works.

```
(fast-exp 2 0)
(fast-exp-iter 2 0 1)
1
(fast-exp 2 1)
(fast-exp-iter 2 1 1)
(fast-exp-iter 2 0 1)
2
(fast-exp 2 3)
(fast-exp-iter 2 3 1)
(fast-exp-iter 2 2 2)
(fast-exp-iter 4 1 2)
(fast-exp-iter 4 0 8)
8
(fast-exp 2 4)
(fast-exp-iter 2 4 1)
(fast-exp-iter 4 2 1)
(fast-exp-iter 16 1 1)
(fast-exp-iter 16 0 16)
16
```

#### Exercise 1.17

This one is simple. Make a version of `fast-exp`

but for multiplication,
assuming `halve`

and `double`

are defined.

```
;; Setup
(define (even? x)
(= (remainder x 2) 0))
(define (double x)
(* x 2))
(define (halve x)
(/ x 2))
;; Solution
(define (mult x y)
(cond ((= y 0) 0)
((even? y) (double (mult x (halve y))))
(else (+ x (mult x (- y 1))))))
```

The solution works just like `fast-exp`

. Where `x`

serves as the
accumulator and `y`

is the step counter. `mult`

will call `double`

until
the counter is `0`

and then go back up the call stack `double`

ing the
previous result. If the counter is ever an odd number, add the
accumulator once and reduce the step counter by one. See the process
shape below.

```
(mult 2 2)
(double (mult 2 1))
(double (+ 2 (mult 2 0)))
(double (+ 2 0))
(double 2)
4
```

#### Exercise 1.18

Make an iterative process for multiplication based on the work in the last two exercises. Simple enough. Just a little translation and some understanding.

```
;; Assume (halve) (double) and (even?) are defined
(define (mult x y)
(define (mult-iter x y a)
(cond ((= y 0) a)
((even? y) (mult-iter (double x) (halve y) a))
(else (mult-iter x (- y 1) (+ a x)))))
(mult-iter x y 0))
```

The iterative process works almost the same way as in ex1.16, where `a`

is used as an accumulator, and `y`

keeps track of the number of times to
double the value of `x`

. Note: the initial value for `a`

must be `0`

.
Here is a sample of the process shape.

```
(mult 10 10)
(mult-iter 10 10 0)
(mult-iter 20 5 0)
(mult-iter 20 4 20)
(mult-iter 40 2 20)
(mult-iter 80 1 20)
(mult-iter 80 0 100)
100
```

#### Exercise 1.19

My math skills are very poor. I worked through this problem on many sheets of paper in my notebook. For me, this was not a simple problem. I eventually got it. This is my explanation for the solution. It may be better to see the Scheme Community’s, Eli Bendersky’s, or Bill The Lizard’s solutions.

Note: I found `p`

and `q`

to be a problem with my slight dyslexia. I am
using `x`

and `y`

for the terms `p`

and `q`

(used in the book)
respectively. The idea is to apply the transformation twice. Then
refactor the problem for `a`

and `b`

to find `y'`

and `x'`

. I cleaned up
my work and took a photo.

![“Exercise 1.19”][png1.19] [png1.19]: /assets/img/sicp/1.19.png “Exercise 1.19”

```
x' = x^2 + y^2
y' = 2xy + x^2
```

```
(define (fib-iter a b x y count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* x x) (* y y)) ;; x'
(+ (* 2 x y) (* y y)) ;; y'
(/ count 2)))
(else (fib-iter (+ (* b y) (* a y) (* a x))
(+ (* b x) (* a y))
x
y
(- count 1)))))
```