module Subvisual::MathUtils::GreatestCommonDivisor

Public Instance Methods

greatest_common_divisor(a, b) click to toggle source
# 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