Euclids Algorithm

Ruby code posted by chaitanya
created at 02 Aug 07:13

Edit | Back
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
class Gcd
  #GCD(m,n)
  # Step 1 : Divide m/n and r is the remainder 0<=r<=n
  # Step 2   if r = 0 then n is the GCD of m,n
  # r !=0 then m =n and n =r go to step 1
  # m can be less than n to make the algorithm faster make sure m is greater than n
  #
  # e.g   2322, 654
  #       1071, 1029
  #       1769,551
  #       2166,6099
  #       163231, 135749
  attr_accessor :m, :n

  def initialize(m, n)
    m, n = m.to_i, n.to_i
    if (m > n)
      @m, @n = m, n
    else
      @m, @n = n, m
    end
    compute(m, n)
  end

  def compute(m, n)
    r = nil #
    p Time.now
    while (r = m % n)!= 0
      m = n
      n = r
    end
    p "The GCD of #{@m}, #{@n} is #{n}"
    p Time.now
  end
end


740 Bytes in 5 ms with coderay