Exercises 1.16, 1.17, 1.18

1.16 Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.

From the hints

• (b^n/2)² = (b²)^n/2
• abⁿ should have the same value through the transition.

I want to decrease the exponent until it equals zero, at which point the result variable, a, will have the result. So the question is, when I halve the exponent n, how can I modify a and b so that abⁿ is unchanged, and that we're somehow closer to the result?

So my strategy is:

• If n is even, halve n, square b, and leave a alone
• If n is odd, decrement n by 1, and multiply a by b.

Here is the procedure.

(define (fast-iter-expt x y)
  (define (fast-helper a b n)
    (cond ((= 0 n) a)
          ((odd? n) (fast-helper (* b a) b (- n 1)))
          ((even? n) (fast-helper a (* b b) (/ n 2)))))
  (fast-helper 1 x y))

1.17 Design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

Referring back to the text for the exponent procedure, I come up with a method for determining multiplication, analogous to the exponentiation method in the text.

• ab = 2(a x ^b⁄₂), if b is even
• ab = a + a(b-1) if b is odd

This translates to the procedure.

(define (double n)
  (+ n n))

(define (halve n)
  (if (even? n)
      (/ n 2)
      (error "Tried to halve an odd number" n)))

(define (mult-r a b)
  (cond ((= b 0) 0)
        ((odd? b) (+ a (mult-r a (- b 1))))
        ((even? b) (double (mult-r a (halve b))))))

1.18 An iterative version of 1.17.

I came up with an invariant quantity, as described in the hint for 1.14

• ab+r = 2a⋅^b⁄₂ + r, when b is even
• ab+r = a(b-1) + (result + a), when b is odd

This translates to the procedure:

(define (mult-i a b)
  (define (multi-helper a b result)
    (cond ((= b 0) result)
          ((odd? b) (multi-helper a (- b 1) (+ result a)))
          ((even? b) (multi-helper (double a) (halve b) result))))
  (multi-helper a b 0))

Exercise 1.12: Pascal's Triangle

The following pattern of numbers is called Pascal's Triangle

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Write a procedure the computes elements of Pascal's triangle by means of a recursive process.

My biggest problem with this exercise was that I didn't understand what it was asking. What input is the procedure supposed to take? I originally thought that I should take a number, and print out that many rows of the triangle. Then I realized I don't really know how to print out data like that in Scheme. So I peeked at a solution online, and realized the procedure is supposed to take the row and column, and return the number. The following procedure does that. The terminating condition for the recursion is when the column is either the first one, or the last one in the row. In both those cases the result is 1.

(define (pascal row column)
  (if (or (= 1 column)
          (= row column))
      1
      (+ (pascal (- row 1) column)
  (pascal (- row 1) (- column 1)))))

Exercise 1.11: Iterative and Recursive Procedures

A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n>=3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

First, the recursive process.

(define (fun-r n)
  (if (< n 3)
      n
      (+ (* 3 (fun-r (- n 3)))
         (* 2 (fun-r (- n 2)))
         (fun-r (- n 1)))))

This was surprisingly straightforward. I thought recursion was hard, but this felt natural. Even more surprising was how hard the iterative version was. I puzzled on it for a while. I finally figured it out aftter I referred back to the discussion of the iterative Fibonnacci procedure in the text.

I'll need to keep three variables and apply the following transformations in each step of the iteration:

a ← a + b + c
b ← a
c ← b

After applying the transformation n times, the results will be

a = f (n + 2)
b = f (n + 1)
c = f (n)

I'll start the process off by initializing the first three terms at 2, 1, 0. The final procedure follows.

(define (fun-iter a b c count)
  (if (= count 0)
      c
      (fun-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

(define (fun n)
  (fun-iter 2 1 0 n))

Iteration, Recursion, and Orders of Growth

This is my notes on section 1.2

Recursion

Many functions can be defined in terms of themselves. The factorial function is an exampe:

$$ n! = n * (n-1)! \\ 0! = 1 $$

It's easy to define a procedure from this definition.

(define (factorial n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

The procedure follows directly from the definition of factorial.

Iteration

The factorial function can also be calculated iteratively. Calculate it by starting with 1, and multiplying each successive integer until we reach our target. For example.

$$ n! = 1 \times 2 \times 3 \times 4 \times ... \times n $$

Translating this to a procedure is often more difficult.

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Iterative processes carry all their state with them from one step of the iteration to the next. Every time the procedure iter is called, all the information necessary to evaluate iter is passed on. Compare to the recursive procedure above, where the expression (* n (factorial (- n 1)) can't be fully evaluated until the the last factorial call reaches the base case of n = 0.

The fact that the Scheme procedure above calls itself doesn't mean that the process is recursive. The key differentiator is whether the procedure call contains all the information it needs to evalute, or whether evaluation is deferred to a future call to the procedure.

Tree recursion

The Fibonacci numbers are another function which can be naturally defined recursively

$$ Fib(0) = 0 \\ Fib(1) = 1 \\ Fib(n) = Fib (n-1) + Fib(n-2) \\ $$

The procedure for this is

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 0))))))

Each call to to Fib where n > 1 generates two more calls to Fib. The + operator has to wait for both of those calls to return before it can evaluate its arguments.

The tree recursive definition of this procedure results in a lot of duplicate work. Figure 1.5 on page 38 illustrates that (fib 3) is computed twice.

Orders of Growth

We're simplifying resources to mean the number of steps taken to solve a given problem, and the amount of space required to solve the problem.

For the recursive factorial procedure above, as the input grows, the number of steps to solve the problem grows at the same rate. The steps grow as Θ(n).

For the iterative factorial procedure, the steps grow as Θ(n), but the space required to calculate is fully capture by the state variables in each iteration, and never grows. The growth of the space is Θ(1).

The tree-recursive Fibonacci sequence requires Θ(φⁿ) steps (where φ is the golden ratio) and space Θ(n).

Some problems can be halved. For example, exponentiation. b⁸ can be calculated as:

$$ b \times b \times b \times b \times b \times b \times b \times b $$

but it can also be calculated as

$$ b^4 \times b^4 $$

\( b^4 \) can be reduced to \( b^2 \times b^2 \) and so on. The steps for calulating exponents this way grow at Θ(log n).

Substitution Model

These are my notes on the discussion from 1.1.3 - 1.1.5 of the text.

The substitution model of process evaluation, as described on page 9 of the text.

To evaluate a combination

1. Evaluate the subexpressions of the combination
2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

Define does not follow the rules above. It is one of several special forms.

To apply a compound procedure: evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

Given the procedures

(define (square x) (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (f n)
  (sum-of-squares (+ n 1) (* n 2)))

We would evaluate (f 5) by the following substitutions
(sum-of-squares (+ n 1) (* n 2)
(sum-of-squares (+ 5 1) (* 5 2)
(+ (square 6) (square 10))
(+ 36 100)
136


This substitution model above uses applicative-order evaluation. An alternative is normal-order evaluation. Normal order evaluation fully expands all arguments before applying procedures.

(f 5)
(sum-of-squares (+ 5 1) (* 5 2)
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

The interpreter actually uses applicative order evaluation, but the substitution model as described here does not accurately capture how the interpreter works.

Structure and Interpretation of Computer Programs

I'm going through Structure and Interpretation of Computer Programs (SICP) on my own. I'm going to use this blog document the materials I use, as well as for my notes and assignments. Here's the resources I'm starting out with:

• The Online Book (Amazon Link for hard copy)
• A YouTube playlist of the lectures
• MIT OpenCourseWare page for 6.001.
• Online Tutor

The videos are from a different delivery than the materals in the OCW site. I'm not sure how closely they'll match up in terms of readings and assignments. Nor am I sure how the online tutor matches.

I'm hardly the first person to blog his way through SICP. Eli Bandersky and Ken Dyck did a similar project. They did a fine job. The only reason I'm repeating is that I think it will help me learn the material. The best way to test your knowledge is to try to explain it to somebody else.