# Revision of *1.2.5 Greatest Common Divisors* from *13 July 2009 - 10:03pm*

The revisions let you track differences between multiple versions of a post.

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 `k`th 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`).

*a*

_{k},

*b*

_{k}), where

*a*

_{k}

__>__

*b*

_{k}, for which Euclid’s Algorithm terminates in

*k*steps. The proof is based on the claim that, if (

*a*

_{k+1},

*b*

_{k+1}) (

*a*

_{k},

*b*

_{k}) (

*a*

_{k-1},

*b*

_{k-1}) are three successive pairs in the reduction process, then we must have

*b*

_{k+1}

__>__

*b*

_{k}+

*b*

_{k-1}. To verify the claim, consider that a reduction step is defined by applying the transformation

*a*

_{k-1}=

*b*

_{k},

*b*

_{k-1}= remainder of

*a*

_{k}divided by

*b*

_{k}. The second equation means that

*a*

_{k}=

*q*

*b*

_{k}+

*b*

_{k-1}for some positive integer

*q*. And since

*q*must be at least 1 we have

*a*

_{k}=

*q*

*b*

_{k}+

*b*

_{k-1}

__>__

*b*

_{k}+

*b*

_{k-1}. But in the previous reduction step we have

*b*

_{k+1}=

*a*

_{k}. Therefore,

*b*

_{k+1}=

*a*

_{k}

__>__

*b*

_{k}+

*b*

_{k-1}. This verifies the claim. Now we can prove the theorem by induction on

*k*, the number of steps that the algorithm requires to terminate. The result is true for

*k*= 1, since this merely requires that

*b*be at least as large as

*F*

*i*

*b*(1) = 1. Now, assume that the result is true for all integers less than or equal to

*k*and establish the result for

*k*+ 1. Let (

*a*

_{k+1},

*b*

_{k+1}) (

*a*

_{k},

*b*

_{k}) (

*a*

_{k-1},

*b*

_{k-1}) be successive pairs in the reduction process. By our induction hypotheses, we have

*b*

_{k-1}

__>__

*F*

*i*

*b*(

*k*- 1) and

*b*

_{k}

__>__

*F*

*i*

*b*(

*k*). Thus, applying the claim we just proved together with the definition of the Fibonacci numbers gives

*b*

_{k+1}

__>__

*b*

_{k}+

*b*

_{k-1}

__>__

*F*

*i*

*b*(

*k*) +

*F*

*i*

*b*(

*k*- 1) =

*F*

*i*

*b*(

*k*+ 1), which completes the proof of Lamé’s Theorem. [back]

Exercises

## 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?

## Comments

## qWKhkAlwZvEGgxEaW

It’s much easier to undretsnad when you put it that way!

## http://www.armaniwatchescollection.co.uk

At 73 years old,

Birkenstock outlethe is still busybirkenstock kairomaking people look good. Giorgio Armani is one of the preeminentBirkenstock UKItalian fashion designers in the world,birkenstock hommestill goingbirkenstock francestrong after 33 years in thebirkenstock kairoindustry. Known for his classically tailored, sleek power suits and clean,armani watcheshigh quality fabrics, everyone from the who’s who of Hollywood to the bankers onarmani watches uk Wall Street have fallen in love with the Armani brand. Now, with over $1.5 billion armani ceramicain revenue and a retail empire that extends to more than 35 countries, Armani himself continues to maintain full control over his business. However, it has been a long, uphill journey for the designer to get where he is today.## Revision of 1.2.5 Greatest Common Divisors from 30 June 2009 - 8

Hola ¿te importaría dejarme saber que alojamiento web

usando ? He cargado un blog en 3 diferentes navegadores de Internet

y debo decir que este blog se carga mucho más

rápido más rápido que la mayoría. ¿Puedes sugerir recomendar una buena internet hosting

proveedor en una honesta precio ? Gracias , se lo agradezco !

Also visit my blog post … Cerrajer

## Revision of 1.2.5 Greatest Common Divisors from 30 June 2009 - 8

Espero con interés escuchar de usted!

Also visit my page Cerrajer

## Revision of 1.2.5 Greatest Common Divisors from 30 June 2009 - 8

Hola ! Alguien en mi Facebook grupo compartió esta página con nosotros, así que vine a darle un aspecto .

Definitivamente estoy disfrutando amando la información .

Estoy bookmarking y estaré twitteando esto a

mis seguidores ! Wonderful blog y excelente diseño y estilo .

Also visit my blog post … Cerrajer

## Post new comment