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