Structure and Interpretation of Computer Programs

         (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)))))

1.2.5  Greatest Common Divisors

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 

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, 

reduces GCD(206,40) to GCD(2,0), which is 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.

42

It is easy to express Euclid’s Algorithm as a procedure: 

(define (gcd a b)

  (if (= b 0)

      a

      (gcd b (remainder a b))))

---

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

involved.

The fact that the number of steps required by Euclid’s Algorithm has logarithmic growth bears an

interesting relation to the Fibonacci numbers:

Lamé’s Theorem: If Euclid’s Algorithm requires k steps to compute the GCD of some pair, then the

smaller number in the pair must be greater than or equal to the kth Fibonacci number.

43

We can use this theorem to get an order-of-growth estimate for Euclid’s Algorithm. Let n be the

smaller of the two inputs to the procedure. If the process takes k steps, then we must have n> Fib (k) 

 k

/  5. Therefore the number of steps k grows as the logarithm (to the base   ) of n. Hence, the order

of growth is   (

log

 n).

Exercise 1.20.  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)

? In the applicative-order evaluation? 

1.2.6  Example: Testing for Primality

This section describes two methods for checking the primality of an integer n, one with order of

growth   (  n), and a ‘‘probabilistic’’ algorithm with order of growth   (

log

 n). The exercises at the

end of this section suggest programming projects based on these algorithms.

Searching for divisors

Since ancient times, mathematicians have been fascinated by problems concerning prime numbers, and

many people have worked on the problem of determining ways to test if numbers are prime. One way

to test if a number is prime is to find the number’s divisors. The following program finds the smallest

integral divisor (greater than 1) of a given number n. It does this in a straightforward way, by testing n

for divisibility by successive integers starting with 2.

(define (smallest-divisor n)

  (find-divisor n 2))

(define (find-divisor n test-divisor)

  (cond ((> (square test-divisor) n) n)

        ((divides? test-divisor n) test-divisor)

        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)

  (= (remainder b a) 0))

We can test whether a number is prime as follows: n is prime if and only if n is its own smallest 

divisor.

(define (prime? n)

  (= n (smallest-divisor n)))

---

The end test for 

find-divisor

 is based on the fact that if n is not prime it must have a divisor less

than or equal to   n.

44

 This means that the algorithm need only test divisors between 1 and   n.

Consequently, the number of steps required to identify n as prime will have order of growth   (  n).

The Fermat test

The   (

log

 n) primality test is based on a result from number theory known as Fermat’s Little 

Theorem.

45

Fermat’s Little Theorem: If n is a prime number and a is any positive integer less than n, then a

raised to the nth power is congruent to a modulo n.

(Two numbers are said to be congruent modulo n if they both have the same remainder when divided

by n. The remainder of a number a when divided by n is also referred to as the remainder of a modulo 

n, or simply as a modulo n.)

If n is not prime, then, in general, most of the numbers a< n will not satisfy the above relation. This

leads to the following algorithm for testing primality: Given a number n, pick a random number a < n

and compute the remainder of a

n

 modulo n. If the result is not equal to a, then n is certainly not prime.

If it is a, then chances are good that n is prime. Now pick another random number a and test it with the

same method. If it also satisfies the equation, then we can be even more confident that n is prime. By

trying more and more values of a, we can increase our confidence in the result. This algorithm is

known as the Fermat test.

To implement the Fermat test, we need a procedure that computes the exponential of a number modulo

another number:

(define (expmod base exp m)

  (cond ((= exp 0) 1)

        ((even? exp)

         (remainder (square (expmod base (/ exp 2) m))

                    m))

        (else

         (remainder (* base (expmod base (- exp 1) m))

                    m))))        

This is very similar to the 

fast-expt

 procedure of section 1.2.4. It uses successive squaring, so that

the number of steps grows logarithmically with the exponent.

46

The Fermat test is performed by choosing at random a number a between 1 and n - 1 inclusive and

checking whether the remainder modulo n of the nth power of a is equal to a. The random number a is

chosen using the procedure 

random

, which we assume is included as a primitive in Scheme. 

Random

returns a nonnegative integer less than its integer input. Hence, to obtain a random number between 1

and n - 1, we call 

random

 with an input of n - 1 and add 1 to the result:

(define (fermat-test n)

  (define (try-it a)

    (= (expmod a n n) a))

  (try-it (+ 1 (random (- n 1)))))

---