fun gcd (x:int,y:int) : int =
case x of 0 => y
| _ => if x < 0 then gcd(y,0-x) else
if y < 0 then gcd(0-y,x) else
if y > x then gcd(y-x,x) else gcd(x-y,y);
"But that's not Perl!"Yeah, yeah, I hear you.
I'll rectify that minor detail in a bit.
But first, an anecdote.
Back in the late nineteennineties, I was studying computer science, and one of the classes was about program specification and verification.
Several of the students already had a background with several programming languages, some were functional, some were imperative, and other languages were a bit confused about what they really were.
When studying program specification and verification, you either become rather obsessed with program correctness -- and hopefully elegance -- or you fail spectactularly.
There are several ways to muster enthusiasm when dealing with such studies; they can be rather, ehrm, theoretical.
I therefore flitted about, flirting with various programming languages, comparing them with the eagerness that young idealists do.
For some reason, I found Euclid's GCD algorithm to be particularly fascinating, for reasons unknown to men to this day.
The Perl version I saw was rather awful, and technically incorrect:
sub gcd {
if (!$_[0]) {
return $_[1];
}
if ($_[1] > $_[0]) {
return gcd ($_[1]-$_[0],$_[0]);
}
return gcd ($_[0]-$_[1],$_[1]);
}Yikes. I mean, eep. And Perl does have a modulo operator.sub gcd {
my ($x, $y) = @_;
$y ? gcd ($y, $x % $y) : abs $x;
}I won't claim that the above code is the epitome of elegance, but it solves the problem in a general and easily read way (I admit a prejudice against $_[N]), while retaining correctness.This is, BTW, one place where some golfers miss the boat; the GCD cannot be a negative integer. That's why the ML code at the top is so verbose.
Small challenges like these kept me going, and it can be an inspiring way to learn details in a new language. So, what would it look like in Perl 6?
sub gcd (Int $x, Int $y) {
$y ?? gcd($y, $x % $y) !! $x.abs;
}What's your favourite algorithm for playtesting languages?
3 comments:
Here's a non-recursive version that is only a little longer:
sub gcd (Int $x is copy, Int $y is copy) {
($x, $y) = ($y, $x % $y) while $y;
$x.abs;
}
While we're talking about GCD in different languages, here are 2 functional variants of how one can formulate it in my Muldis D language:
function gcd (NNInt <-- $x : NNInt, $y : NNInt) {
$y = 0 ?? $x !! nlx.lib.gcd( $y, $x % $y )
}
function gcd (NNInt <-- $x : NNInt, $y : NNInt) {
if $y = 0 then $x else nlx.lib.gcd( $y, $x mod $y )
}
As a follow-up to my previous post, all of the relevant parts of the Muldis D language have now been formally specced, with CPAN release 0.124.0 and, inspired by your blog post, here is a code example in the spec:
updater make_coprime (&$a : NNInt, &$b : NNInt) {
with function gcd (NNInt <-- $a : NNInt, $b : NNInt) {
$b = 0 ?? $a !! rtn( a => $b, b => $a mod $b round Down )
}
$gcd ::= nlx.lib.gcd( $>a, $>b )
$a := $a div $gcd round Down
$b := $b div $gcd round Down
}
Post a Comment