Author: Philip Potter

Specification

P32 (**) Determine the greatest common divisor of two positive integer
    numbers.  Use Euclid's algorithm.

Example

> say gcd(36,63);
9

Source code: P32-rhebus.pl

use v6;

# Example 1: iterative
#   we specify type constraints on our input parameters
sub gcdi (Int $a is copy, Int $b is copy) {
    while $a % $b {
        ($a,$b) = ($b, $a % $b);
    }
    return $b;
}

gcdi(36,63).say;

# Example 2: recursive
#   This can take advantage of a tail-call optimization, if the compiler
#   supports it
#   $a %% $b is true iff $b divides $a evenly. It is equivalent to:
#   !($a % $b)
sub gcdr (Int $a, Int $b) {
    return $b if $a %% $b;
    return gcdr($b, $a % $b);
}

gcdr(36,63).say;
gcdr(63,36).say;

# Example 3: series operator
#   The series operator generates series lazily. It takes some start terms, a
#   generation rule, and possibly a limit, and produces a series.
#   To create the Fibonacci series, we write:
#       (1, 1, *+* ... *)
#   The generation rule is to sum the previous two terms: *+*.
#   A limit of * continues the series forever.
#
#   We exploit this to generate the series of intermediate values in Euclid's
#   algorithm: each step in the series is the mod of the last two terms. When
#   we reach 0, the term before that was the gcd.
sub gcds (Int $a, Int $b) {
    return ($a, $b, *%* ... 0)[*-2];
}

gcds(8,12).say;
gcds(36,63).say;
gcds(63,36).say;