Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!veritas!amdcad!light!bvs
From: bvs@light.uucp (Bakul Shah)
Newsgroups: comp.lang.postscript
Subject: GCD algorithm (was Re: Color Spirograph (!))
Message-ID: <1990Oct31.182705.3184@light.uucp>
Date: 31 Oct 90 18:27:03 GMT
References: <90302.140837CXT105@psuvm.psu.edu>
Reply-To: bvs@light.UUCP (Bakul Shah)
Organization: Bit Blocks, Inc.
Lines: 62

In article <90302.140837CXT105@psuvm.psu.edu> CXT105@psuvm.psu.edu (Christopher Tate) writes:
> ...
>I will mention again, though, that this code contains a very well-behaved
>implementation of Euclid's classic algorithm for calculating the Greatest
>Common Divisor of two integers.  Anyone who's looking for such a beast,
>feel free to borrow it!

A couple of comments on the GCD algorithm.

- To justify posting this to a PostScript group, here is a faster
  version of basically the same algorithm:

    /gcd {              % given m, n on the stack
      dup 3 1 roll mod  % leaves n, m mod n on the stack
      dup 0 eq {
	pop             % leaves n on the stack when done
      } {
	gcd             % find gcd of the new pair
      } ifelse
    } bind def

  Not too surprisingly, this recursive version is faster than
  the one below which uses an explicit loop:

    /gcd {
      { dup 3 1 roll mod dup 0 eq { pop exit } if } loop
    } bind def

- I discovered a curious fact when I looked through a bunch of
  math/CS books for an exact description of Euclid's algorithm.
  The three math books I looked at describe the _faster_ algorithm
  (the one used in the spirograph program) as Euclid's alg., while
  the three CS books describe the following _slower_ one as
  Euclid's:

    /* using guarded commands... */
    loop {
      a > b => a -= b;
      b > a => b -= a;
    }

    The loop terminates when neither guard is true, i.e. when
    a == b.  This extends in a nice (but slow) way for the GCD
    of N numbers.  As an example, gcd(a, b, c, ... n) is

    loop {
      a > b => a -= b;
      b > c => b -= c;
      c > d => c -= d;
      ...
      n > a => n -= a;
    }

  So....  Who is right?  How did two different alg. came to be
  known as Euclid's?  Does the faster alg. also have such a nice
  generalization for gcd of N numbers?  The slower alg. can be
  modified slightly to simulteneously compute LCM.  Can the same
  thing be done with the faster one?  Time to visit a library!

-- Bakul Shah
   bvs@BitBlocks.COM
   ...!{ames,decwrl,sun,uunet}!amdcad!light!bvs