[Tutor] Help Needed [greatest common divisor]

Danny Yoo dyoo@hkn.eecs.berkeley.edu
Sun, 14 Apr 2002 16:28:30 -0700 (PDT)


On Sun, 14 Apr 2002, Bob Rea wrote:

> On Sunday 14 April 2002 03:10 am, Michael Williams wrote:
> > One more bit of advice - pay attention in your maths
> > classes! They're really important for programming.
>
> I owuld second that strongly. I have been trying to learn to program my
> own self and the math involved is something I know nothing about I had
> algebra and palne geometry in high school and thats it.
>
> an example: Chun, ch 5, exercise 15, "Determine the
> greatest common divisor and least common multiple of a pair
> of integers."

Let's say that we have a fraction that hasn't been reduced to lowest terms
yet.  Here's an example of such a fraction:

    42
    --
     8

A common divisor is some number D that we can use to divide a group of
numbers.  For example, if we have 42 and 8, a common divisor of those two
numbers could be 2, since 2 divides 42 and it also divides 8.

The "Greatest Common Divisor" is just the largest number we can use that
will divide two numbers neatly.  In the example with 42 and 8, we can
figure it out by successively checking numbers:

    Does 1 divide 42 and 8?
    Does 2 divide 42 and 8?
    ...

At some point, we should be able to figure out when there aren't any more
common divisors we can look for, so this search won't take forever.


This is one way of figuring out what the greatest common divisor is... but
it's not the only way!  This question is a classic one in computer
science; if you get the chance, look up in your library or favorite search
engin the topic of "Euclid's Algorithm", and you should see something
interesting.


Best of wishes to you!