Examining the difference between θ(n) and θ(log(n)) growth with successive squaring.
Design an iterative exponentiation process using successive squaring
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
This one is simple. Make a version of
fast-exp but for multiplication,
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
x serves as the
y is the step counter.
mult will call
the counter is
0 and then go back up the call stack
previous result. If the counter is ever an odd number, add the
accumulator once and reduce the step counter by one. See the process
(mult 2 2) (double (mult 2 1)) (double (+ 2 (mult 2 0))) (double (+ 2 0)) (double 2) 4
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
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
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
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
q to be a problem with my slight dyslexia. I am
y for the terms
q (used in the book)
respectively. The idea is to apply the transformation twice. Then
refactor the problem for
b to find
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)))))