From: vanjac12@... (Van Jacques)
Date: 2003-12-12T09:46:58+09:00
Subject: Re: prog for g.c.d. of 2 integers

Peter <Peter.Vanbroekhoven@cs.kuleuven.ac.be> wrote in message news:<Pine.LNX.4.44.0312112024020.11559-100000@merlin.cs.kuleuven.ac.be>...
> > If you put this test into the function, it is more general because then
> > arguments can be placed in any order.
> 
> Actually you don't need the test since
> 
>   a, b = b, a % b
> 
> swaps a and b if b > a. Well, as long as only positive numbers are
> involved...
> 
> Peter

Good point. a % b = a if b > a . Also, I liked Robert's solution,

a, b = b, a % b  while b !=0 
  
though I didn't understand the language for n > 2.

My less elegant solution for an the g.c.d of n numbers follows.

This has to be done by pairs. For 3 numbers (a,b,c),
one finds gcd(a,b), and then

gcd(a,b,c) = gcd(gcd(a,b),c),  and so on.

This program does it.

=============
#!/usr/bin/ruby -w

# num = no. of numbers
# mod(x,y) should be replaced by Robert's suggestion above.

def mod(x,y)
  z = x % y
  if z == 0
    return y
  else
    w = mod(y,z)
  end
end

puts "Enter the number of numbers for greatest common denominator."

num = gets.chomp.to_i

a = Array.new
b = Array.new
gcd = Array.new

for i in 0...num
  a[i] = rand(999) + 1
end
puts a
b = a.sort.reverse
puts b
gcd[0] = mod(b[0],b[1])

for i in 2...num
if (b[i] > gcd[i-2])
  gcd[i-1] = mod(b[i],gcd[i-2])
else 
  gcd[i-1] = mod(gcd[i-2],b[i])
end
end
puts gcd[num-2]
===========

Van