greatest_common_divisor.pony

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
primitive GreatestCommonDivisor
  """
  Get greatest common divisor of x and y.

  Providing 0 will result in an error.

  Example usage:

  ```pony
  use "math"

  actor Main
    new create(env: Env) =>
      try
        let gcd = GreatestCommonDivisor[I64](10, 20)?
        env.out.print(gcd.string())
      else
        env.out.print("No GCD")
      end
  ```
  """
  fun apply[A: Integer[A] val](x: A, y: A): A ? =>
    let zero = A.from[U8](0)
    if (x == zero) or (y == zero) then
      error
    end

    var x': A = x
    var y': A = y

    while y' != zero do
      let z = y'
      y' = x' % y'
      x' = z
    end

    x'