Being from a musician's background as opposed to computer science, I have a bit of an inferiority complex when it comes to hard core theory such as algorithms and such. Lately I've been trying to make amends by hacking though such classics as
.
This morning I decided to write out Euclid's algorithm from page 2 of Knuth. First I wanted to do it exactly as it was written in the book:
#!/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;
}}
}
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;
}
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;
}
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.
()-()
\"/
`