- Work in Emacs
- Split your screen in 2 (C-x 2)
- Run scheme in one window (M-x run-scheme)
- Edit your file in the other window (C-x o switch among windows)
- To load a complete file in scheme type (load "a.scm") in scheme.
- In case you are not in the right directory, type (chdir "mydir") in scheme
- To send a definition of a function from the buffer to the scheme process, put the cursor in the body of the function at do M-C-x

- Iterative Fast Exponentiation (1.16 from book)
- Logarithmic Fibonacci (1.19 from book)
- Product higher order function (1.31 from book)
- Accumulate higher order function (1.32 from book)

`fast-exp`

.
**Hint:** Using the observation that
(b^{n/2})^{2}=(b^{2})^{n/2}, keep along with
the exponent n and the base b, an additional state variable a, and define the
state transformation in such a way that the product ab^{n} is unchanged
from state to state. At the beginning of the process, a is taken to be 1, and
the answer is given by the value of a at the end of the process. In general,
the technique of defining an *invariant quantity* that remains unchanged
from state to state is a powerful way to think about the design of iterative
algorithms.

For reference, the recursive version of `fast-exp` is:

(define (fast-exp b n) (cond ((= n 0) 1) ((even? n) (square (fast-exp b (/ n 2)))) (else (* b (fast-exp b (- n 1))))))

a <- a + b b <- aCall this transformation T. Observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n+1) and Fib(n). In other words, the Fibonacci numbers are produced by applying T

Now consider T to be the special case of p=0 and q=1 in a family of
transformations T_{pq}, where T_{pq} transforms the pair
(a,b) according to:

a <- bq + aq + ap b <- bp + aqShow that if we apply such a transformation T

This gives us an explicit way to square these transformations, and thus we
can compute T^{n} using successive squaring, as in the
`fast-exp`

procedure. Put this all together to complete the following
procedure, which runs in logarithmic number of steps:

(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b <??> ;; compute p' <??> ;; compute q' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

(define (sum term a next b) (if (< b a) 0 (+ (term a) (sum term (next a) next b))))The

`sum`

procedure is only the simplest of a vast number of
similar abstractions that can be captured as higher-order procedures.
Write a similar procedure called product that returns the product of the
values of a function at points over a given range. Show how the factorial
function can be defined in terms of product.
If your product procedure generates a recursive process, write one
that generates an iterative process. If it generates an iterative
process, write one that generates a recursive process.
The end.