From: vanjac12@... (Van Jacques)
Date: 2003-12-11T22:27:00+09:00
Subject: prog for g.c.d. of 2 integers

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 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.