#!/usr/bin/perl

use strict;
use warnings 'all';
use integer;

=head1 Euclid's Algorithm

Given two positive integers m and n, find their greatest common 
divisor.

=cut

sub p
{
    my ($m, $n) = ($_[0], $_[1]);
    my $r;
  
    # m and n must be positive integers.
    if (($m < 1) || ($n < 1)) {
        die("Values must be positive integers.");
    }

    # E0: If m < n, exchange m and n
    #
    # As Knuth points out, this step can be avoided,
    # but it will force the algorithm to go through
    # another loop as it exchanges m and n when n is
    # greater.
    if ($m < $n) {
        ($m, $n) = ($n, $m);
    }

    do {{
        # E1: Divide m by n and let r be the remainder
        $r = $m % $n;
        # E2: If r = 0, the algorithm terminates; $n is the answer
        if ($r == 0) {
            return $n;
        }
        # E3: Set m = n, n = r, and go back to step E1.
        $m = $n;
        $n = $r;
        redo;
    }} 
}
[download]

But this didn't seem nearly Pearly enough for me. Since I always seem to get paid for programming in just about anything BUT my language of choice, I am not very good with "idiomatic Perl". Thus I set out to try to write the thing as Perl-like as I could:

sub p_idiomatic
{
    # Use a numeric sort to enforce that m is greater then n
    my ($m, $n) = sort { $b <=> $a } $_[0], $_[1];

    # This is the same as:
    # my ($m, $n) = reverse sort { $a <=> $b } $_[0], $_[1];

    # Holds the remainder
    my $r;

    # Insure that they are positive integers
    # Is their a better way to do this?
    if (($m < 1) || ($n < 1)) {
        die("Values must be positive integers.");
    }
    do {{
        $r = $m % $n;
        $m = $n;
        $n = $r;
    }} until $r == 0;

    return $m;
}
[download]

Then I wondered if anyone else here had done this, so I tried Super Search. That's when I found this from Tilly's Continued Fractions:

sub gcd {
  my ($n, $m) = @_;
  while ($m) {
    my $k = $n % $m;
    ($n, $m) = ($m, $k);
  }
  return $n;
}
[download]

Short and sweet and very clean.

Tilly, if you are reading this somewhere, thanks! Even though you are no longer here, I've learned a lot from your posts.

()-()
 \"/
  `