Module: Subvisual::MathUtils::GreatestCommonDivisor

Included in:
Subvisual::MathUtils
Defined in:
lib/subvisual/math_utils/greatest_common_divisor.rb

Instance Method Summary collapse

Instance Method Details

#greatest_common_divisor(a, b) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/subvisual/math_utils/greatest_common_divisor.rb', line 6

def greatest_common_divisor(a, b)
  d = 0

  while a.even? && b.even?
    a /= 2
    b /= 2
    d += 1
  end

  while a != b
    if a.even?
      a /= 2
    elsif b.even?
      b /= 2
    elsif a > b
      a = (a - b) / 2
    else
      b = (b - a) / 2
    end
  end

  2**d * a
end