# brian_hassinger

software developer

## Exponentiation

February 07, 2013

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(bn) never changes from step to step
• (b2)n/2 - square of b raised to n/2
• the state variable starts at 1
• bn = b * bn-1
• b0 = 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 bn = (b2)n/2, if the exponent is odd then bn = b * bn-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)))))
``````