# P32 - Determine the greatest common divisor of two positive integer

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;

```