Euclidean algorithm (Python)

From LiteratePrograms

Other implementations: C | Erlang | Forth | Haskell | Java | Java, recursive | OCaml | Prolog | Python | Scala | Standard ML

a brief definition

def gcd(a,b):
        """ the euclidean algorithm """
        while a:
                a, b = b%a, a
        return b

or using recursion:

def gcd(a,b):
        """ the euclidean algorithm """
        if b == 0:
                return a
        else:
                return gcd(b, (a%b))

a brief digression

The Euclidean Algorithm having been, and Knuth having devoted over 40 pages to it in The Art of Computer Programming, there is very little to say about the implementation that can not be more profitably found elsewhere, such as the other language versions on this site.

We will, however, reflect a bit on the following text:

A program without a loop and a structured variable isn't worth writing. — Alan J. Perlis

This program obviously clears the hurdle Perlis places for being worth writing. It has a loop – an unbounded loop? – and it has a structured variable in the form of the pair of arguments – (a, b).

What is not so obvious is that it is also a microcosm of expression evaluation. When we evaluate an expression, in general we either use a projection operator in the code (head/tail, car/cdr, composite.component, [array element], etc.) to select a portion of the data and ignore the rest, or we use an injection tag in the data to select a portion of the code (if/else, case, subtype or polymorphic dispatch, etc.) and ignore the rest, and the evaluation terminates when we can no longer make any reductions of either type. In the GCD computation, we abstract all of that away, and instead use the modulo operator to select a portion of the arguments' factorizations, and ignore the rest. The swapping of the roles of the a and b arguments reflects the interleaving of selection (data chooses code) and projection (code chooses data) during evaluation, and gcd() terminates just when it fails to find any more possible reductions.

This abstraction in terms of prime factors means that the variables are even more structured than we had first remarked. Our state, in fact, consists of a pair of lists of prime factors. This structure comes in handy when considering that potentially unbounded loop. On each pass through the loop, we either toss out some unmatched factors, or swap the variables so we are in a position to do so on the next iteration. Unless we are in a position to pass in as an argument, we must eventually reduce both arguments to duplicate lists of shared factors, and so the calculation converges.

When passing from this simple model to actual code, we lose the assurance of termination. Part of the problem is that running code not only consists of evaluating expressions, but also applying abstractions. In evaluation, as in following a river network downstream, the structures become simpler over time. As soon as we add the possibility of application, as in following the ramifications of tree branches from the trunk out to the leaves, the structures become more complex over time. In general, therefore, unbounded loops which contain applications may not converge as nicely.

Question 1. when is it desirable to code a program that can be shown not to terminate?

Exercise 2. take a solution for non-termination and apply it to the Blue Screen Of Death.

Question 3. what is the relationship of logical cuts (and cut-free proofs) to function application?

Exercise 4. find a well-known historical algorithm that expresses the essence of apply (like the GCD computation expresses the essence of eval) – and add it to this site

Download code