Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newtonâ€™s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

Consider the problem of computing the exponential of a given number. We would like a procedure that takes as arguments a base b and a positive integer exponent n and computes b n . One way to do this is via the recursive definition

$$ b^n = b \cdot b^{n-1} $$ $$ b^0 = 1 $$

which translates readily into the procedure

```
(defn expt [b n]
(if (= n 0)
1
(* b (expt b (dec n)))))
```

This is a linear recursive process, which requires $\Theta(n)$ steps and $\Theta(n)$ space. Just as with factorial, we can readily formulate an equivalent linear iteration:

```
(defn expt-iterative [b counter product]
(if (= counter 0)
product
(recur b
(dec counter)
(* b product))))
(defn expt [b n]
(expt-iterative b n 1))
```

This version requires $\Theta(n)$ steps and $\Theta(1)$ space. We can compute exponentials in fewer steps by using successive squaring. For instance, rather than computing $b^8$ as

$$ b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot b)))))) $$

we can compute it using three multiplications:

$$ b^2 = b \cdot b $$ $$ b^4 = b^2 \cdot b^2 $$ $$ b^8 = b^4 \cdot b^4 $$

This method works fine for exponents that are powers of 2. We can also take advantage of successive squaring in computing exponentials in general if we use the rule:

$$ b^n = (b^{n/2})^2 \text{ , n even } $$

$$ b^n = b \cdot b^{n-1} \text{ , n odd} $$

We can express this method as a procedure:

```
(defn fast-expt [b n]
(cond (= n 0)
1
(even? n)
(square (fast-expt b (/ n 2)))
:else
(* b (fast-expt b (dec n)))))
```

The process evolved by fast-expt grows logarithmically with $n$ in
both space and number of steps. To see this, observe that computing
$b^{2n}$ using `fast-expt`

requires only one more multiplication than
computing $b^n$ . The size of the exponent we can compute therefore
doubles (approximately) with every new multiplication we are
allowed. Thus, the number of multiplications required for an exponent
of $n$ grows about as fast as $\log_2 n$. The process has $\Theta(\log n)$
growth.

The difference between $\Theta(\log n)$ growth and
$\Theta(n)$ growth becomes striking as $n$ becomes large. For
example, `fast-expt`

for n = 1000 requires only 14 multiplications. It
is also possible to use the idea of successive squaring to devise an
iterative algorithm that computes exponentials with a logarithmic
number of steps

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

(Hint: Using the observation that $(b^{\frac{n}{2}})^2 = (b^2 )^\frac{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.)