Recounting the Rationals, part IVb: the Euclidean Algorithm

Suppose we have two integers, and we’d like to find their greatest common divisor (GCD). Recall that the greatest common divisor of two integers m and n is exactly that: the greatest integer which is a divisor of both m and n. The obvious way to do this—which is probably the way you learned in elementary school, when reducing fractions—is to factor each integer into primes, and look for overlap. For example, let’s say we want to find the GCD of 450 and 525. We begin by factoring:

\begin{array}{rcl}  450 & = & 2 \cdot 3^2 \cdot 5^2 \\   525 & = & 3 \cdot 5^2 \cdot 7  \end{array}

Now we pull out as many prime factors as we can which are contained in the factorizations of both numbers. We can’t use 2 at all, since it is only contained in the factorization of 450; we can use a factor of 3, but only one; and we can use two factors of 5. Putting these together, the greatest common divisor of 450 and 525 is 3 \cdot 5^2 = 75.

This method is intuitive, and works well for relatively small numbers, but (there’s always a “but”, isn’t there?) it fails horribly for larger numbers. For example, what if you wanted to find the GCD of 2257394839 and 45466644967? (Go ahead, try it! =) The problem is that factoring is hard, even for computers—where by “hard” I mean “hard to do quickly”. It’s easy to write computer programs to do factoring, it’s just that no one knows how to write a program which factors large numbers quickly. (By “large” in this context I mean numbers with hundreds of digits; the two numbers I gave as an example above could be factored very quickly by a computer, but I bet YOU can’t factor them quickly, so the point is the same.)

Well, as you probably guessed, there’s a better algorithm for calculating the GCD of two numbers, since the GCD can actually be found without any reference to factorizations. This better algorithm is called the Euclidean Algorithm, in honor of Euclid, the first mathematician to write it down (around 300 BC, making it one of the oldest algorithms known!). It’s based on the property I showed (and proved) in my last post, namely, that

\gcd(m,n) = \gcd(m,n-m).

(Technically, in my last post I showed that \gcd(m,n) = \gcd(m,m-n), but since anything that divides x also divides -x, we can flip around the m-n if we want: anything that divides m-n will also divide -(m-n) = n-m, and vice versa.) Here’s how it works:

  1. Given two integers m and n, if they are the same, then clearly they are equal to their greatest common divisor.
  2. Otherwise, reduce the larger of the two numbers by subtracting the smaller number from it.
  3. Lather, rinse, repeat.

That’s it. Were you expecting something more complicated? We already know that doing the subtraction step doesn’t change the GCD, and since the numbers are always getting smaller, the algorithm must eventually stop. Genius! That Euclid was one smart dude. Anyway, let’s try it on a simple example: finding the GCD of 56 and 20.

  1. 56 is greater than 20, so subtract 20 from 56, leaving 36 and 20.
  2. 36 is still greater than 20, so subtract 20 again, leaving 16 and 20.
  3. Subtract 16 from 20, leaving 4 and 16.
  4. Subtract 4 from 16 three times, eventually leaving 4 and 4.
  5. Hence the GCD of 56 and 20 is 4! (This is easy to verify by factoring.)

Neat! But… what has all this got to do with the Calkin-Wilf tree? Well, if you haven’t already noticed, the Euclidean algorithm is exactly the same as the method for finding your way “up” the Calkin-Wilf tree! In particular, since all the rationals in the Calkin-Wilf tree are in lowest terms, finding your way up the Calkin-Wilf tree from m/n exactly corresponds to using the Euclidean Algorithm on m and n in order to show that their GCD really is 1. And in general, if \gcd(m,n) = d, running the Euclidean Algorithm on m and n is like finding your way up a Calkin-Wilf tree in which all the numbers have been multiplied by d (so that it starts at d/d instead of 1/1). In an important sense, we can say that the Calkin-Wilf tree is the Euclidean Algorithm, in tree form!

In closing, I should note that in practice there’s a slight improvement we can make upon the basic Euclidean Algorithm. To see what it is, consider running the Euclidean Algorithm on 20451 and 2. Well, 20451 is bigger than 2, so subtract 2 from 20451, leaving 20449 and 2. Subtract 2 again, leaving 20447 and 2. 20447 is still bigger than 2, so subtract… this is the point where we start getting very bored. Everyone can see perfectly well that since 20451 is odd, after subtracting 2 enough times, we will eventually be left with 1. So this suggests our practical improvement: at each step, instead of replacing the larger number by the remainder when subtracting the smaller number, replace it by the remainder when dividing it by the smaller number—since division can be viewed as repeated subtraction. Now, using this improved method, can you find the GCD of 2257394839 and 45466644967?

About these ads
This entry was posted in computation, iteration, number theory. Bookmark the permalink.

15 Responses to Recounting the Rationals, part IVb: the Euclidean Algorithm

  1. Dave Eaton says:

    I couldn’t explain exactly how I found your blog- I hopped from a ‘stumbled upon’ site to a link and to another- but I just want to say that this is great stuff, and you present it quite well.

    I read your post about wondering whether it’s worth all the work you put into a blog. One of the great things about blogs is that they store well. I’m always amazed at the quality of writing I encounter in blogs that are, sadly, now defunct.

    In any case, now that I know you are here, I’m looking forward to reading more. Good stuff.

  2. Brent says:

    Dave: thanks! I appreciate the encouragement. However you found me, I’m glad you did—and I hope you continue to enjoy the posts! =)

  3. DB says:

    Great stuff! About time I learned an algorithm that’s 2300 years old. Here’s how I coded it in R:


    euclid <- function(a, b) repeat {
    if (!(a <- a %% b)) return(b)
    if (!(b <- b %% a)) return(a)
    }

    > euclid(45466644967, 2257394839)
    [1] 373679

  4. Jesse says:

    I too am enjoying these very much.

    One request though: would it be possible to use transparent backgrounds for the math graphics? I usually read these in an RSS reader with an off-white background.

  5. Brent says:

    Jesse: hmm, good question. I’ll look into that…

  6. Brent says:

    Jesse: I went to look at the code that generates the LaTeX images, and to my surprise I found that there was code there to make the background transparent just as you request, but it was commented out, and I couldn’t remember why. So I uncommented and tested it, and now I remember why: the -transparent option to the ‘convert’ utility apparently does not play well with anti-aliasing, and the formulas come out looking all patchy and full of holes and unreadable. =( So, for now, I hope you can live with the white backgrounds…

  7. Jesse says:

    Brent: sure, no biggie. Out of curiosity, how are the images generated? I know in the past there have been issues with ImageMagick and transparency; in fact I worked on a little patch to a program called L2P (http://redsymbol.net/software/l2p/) to help with this.

  8. Brent says:

    Jesse: they are generated by injecting the LaTeX code into a minimal LaTeX document, running it through latex to produce a .ps file, and then using ImageMagick’s convert to make it into a .png. Sounds like exactly what l2p does. How does l2p get nice transparency?

  9. Jesse says:

    Brent: Yep, that is just like l2p. Here’s an example of how it runs convert:


    convert -matte -fuzz 20% -transparent #ffffff -units PixelsPerInch -density 300 /path/to/.ps /path/to/.png


    $ convert --version
    Version: ImageMagick 6.3.7 02/09/08 Q16 http://www.imagemagick.org

  10. Raf says:

    hello

    Great efforts here :D

    how about fourier siries and fourier transformation next?

    and put up some history, that’ll make it more interesting

    and maybe some more graphical representations?

    image/flash/video?

    *thumb up*

  11. Pingback: Carnival of Mathematics 1000 « JD2718

  12. Note to generate nice math pngs I’ve found mathml -> svg -> png a good process, with the processing done with mathmlsvg and gimp respectively.
    These tools came as standard with my Fedora 7 distribution at least.
    You can see example output here:

    http://www.pixelbeat.org/docs/google_gender_ratio_puzzle/

    Also here is the Euclidean algorithm for GCD implemented
    in the unix bc language: http://www.pixelbeat.org/scripts/bc

    p.s. I “stumbledupon” this page. Now subscribing…

  13. Pingback: The hyperbinary sequence and the Calkin-Wilf tree « The Math Less Traveled

  14. Albert says:

    PNGs with an alpha layer for gradient transparencies work fine in all browsers except for MSIE. There is are plenty of javascript workarounds though.

  15. Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled

Comments are closed.