# 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;