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

The greatest common divisor (GCD) of two integers a and b is defined to be the largest integer that divides both a and b with no remainder. For example, the GCD of 16 and 28 is 4. In Chapter 2, when we investigate how to implement rational-number arithmetic, we will need to be able to compute GCDs in order to reduce rational numbers to lowest terms. (To reduce a rational number to lowest terms, we must divide both the numerator and the denominator by their GCD. For example, 16/28 reduces to 4/7.) One way to find the GCD of two integers is to factor them and search for common factors, but there is a famous algorithm that is much more efficient.

The idea of the algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r . Thus, we can

use the equation

```
GCD(a,b) = GCD(b,r)
```

to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,

```
GCD(206,40) = GCD(40,6)
= GCD(6,4)
= GCD(4,2)
= GCD(2,0)
= 2
```

It is possible to show that starting with any two positive integers
and performing repeated reductions will always eventually produce a
pair where the second number is `0`

. Then the GCD is the other number
in the pair.

This method for computing the GCD is known as *Euclid’s Algorithm*, it
is easy to express it as a procedure:

```
(defn gcd [a b]
(if (= b 0)
a
(recur b (rem a b))))
```

This generates an iterative process, whose number of steps grows as the logarithm of the numbers involved.

The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in Section 1.1.5. (The normal-order-evaluation rule for if is described in Exercise 1.5.)

Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed.

How many remainder operations are actually performed in:

- the normal-order evaluation of (gcd 206 40) ?
- the applicative-order evaluation?