Algorithums in Ruby

Greatest Common Divisor

Ruby has a native implementation of the greatest common divisor.

1
2

  20.gcd(15)
  => 5

However as a pure academic exercise lets implement Euclid’s algorithm for finding the greatest common divisor between any number of numbers in ruby!

1
2
3
4
5
6
7

  def gcd(u, v)
    if v.zero?
      return u
    else
      gcd(v, u.modulo(v))
    end
  end

Greatest Common Divisor for three numbers

1
2
3

  def gcdt(u, v, w)
    gcd(gcd(u, v), w)
  end

Extending this to a generic algorithm that can take any number of numbers

1
2
3
4
5
6
7
8

  def gcd_any(*args)
    raise ArgumentError 'Need at least two numbers' if args.length < 2

    start = args.shift
    args.inject(start) do |result, value|
      gcd(result, value)
    end
  end

Comments