Module: Math

Defined in:
lib/ext/math.rb

Class Method Summary collapse

Class Method Details

.gcd(a, b) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
 
# File 'lib/ext/math.rb', line 2

def self.gcd(a, b)
  # trivial case first: gcd(a, 0) == 1*a + 0*0
  return 1, 0 if b == 0

  # recurse: a = q*b + r
  q, r = a/b, a%b
  s, t = gcd(b, r)

  # compute and return coefficients:
  # gcd(a, b) == gcd(b, r) == s*b + t*r == s*b + t*(a - q*b)
  return t, s - q * t
end