From: Robert Klemme <bob.news@...>
Date: 2003-12-12T00:42:10+09:00
Subject: Re: prog for g.c.d. of 2 integers


"Van Jacques" <vanjac12@yahoo.com> schrieb im Newsbeitrag
news:70ae81fd.0312110524.309e73c0@posting.google.com...
> Topics from mathematics make good practice programs, IMO.
> Comments are welcome.
>
> First we need a program that will give the greatest
> common denominator (g.c.d.) of 2 (then of n) numbers,
> denoted (a,b) (or (a_1,a_2,...,a_n)) and the least
> common multiple (l.c.m.), denoted [a,b].
> (This will verify the theorem that (a,b)[a,b] = ab).
>
> First, a program to give the g.c.d of 2 integers.
> This shows the steps I went through writing this.
> I hope they are of some use or interest to someone.
>
> Use the Euclidean algorithm.
>
> The following is not a program, but work towards a program
> (see the end for the program).
>
> Choose numbers a and b between 1 and 999, so
> the program will start with
>
> a = rand(999) + 1
> b = rand(999) + 1
>
> #  make sure that a > b
>
> if b > a
>   a,b = b,a
> end
>
> # The Euclidean algorithm; a = r_0 , b = r_1
> # r_2 = r_0 % r1 = a % b ; r_i = r_(i-2) % r_(i-1)  for i = 2,3,...,n
> # till r_n = 0. The g.c.d. = r_(n-1)
>
> r_2 = a % b
>
> if r_2 == 0
>   gcd = b
> end
>
> r_3 = b % r_2
>
> if r_3 == 0
>   gcd = r_3
> end
>
> We need to do this recursively until we get 0.
> We want a function or method that takes 2 integers x > y
> and if x % y = 0, y is the gcd and that part
> of the program is done. If x % y is not 0, we keep applying
> r_i = r_(i-2) % r_(i-1) until we get 0,
> in which case r_(i-1) = gcd.
>
> I think this will work:
> ==============
> def mod(x,y)
>   z = x % y
>   if z == 0
>     return y
>   else
>     w = mod(y,z)
>   end
> end
>
> a = rand(999) + 1
> b = rand(999) + 1

If you put this test into the function, it is more general because then
arguments can be placed in any order.

> if b > a
>   a,b = b,a
> end
>
> gcd = mod(a,b)
> puts a.to_s + "   " + b.to_s + "  g.c.d. is  " + gcd.to_s
> ==========
>
> I tested this and it does work. So now to extend to the
> g.c.d. of n numbers--see my next post, unless someone
> else does it first.

Here are two implementations that don't use recursion since this is more
efficient.

def gcd2(a,b)
  raise ArgumentError, "Value out of range" if a <= 0 || b <= 0

  a,b = b,a if b > a

  begin
    a,b = b,a % b
  end while b != 0

  a
end

def gcd3(*num)
  raise ArgumentError, "Value out of range" if num.detect{|n|n<=0}

  case num.size
  when 1
    raise ArgumentError, "too few arguments"
  when 2
    a,b = num
    a,b = b,a if b > a

    begin
      a,b = b,a % b
    end while b != 0

    a
  else
    num.inject{|a,b| gcd3(a,b)}
  end
end

Kind regards

    robert