Re: prog for g.c.d. of 2 integers

"Van Jacques" <[e-mail]> schrieb im Newsbeitrag
news:[e-mail]...
> Peter <[e-mail]> wrote in message
news:<[e-mail]>...
> > > 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.

I've stripped the superfluous stuff and corrected the error check (0 is
the error case, not 1):

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

  case num.size
  when 0
    raise ArgumentError, "too few arguments"
  when 2
    a,b = num
    a,b = b,a % b until b == 0
    a
  else
    num.inject{|a,b| gcd3(a,b)}
  end
end

About the gcd-n part: inject just does works the way you describe the algo
for n numbers.  It yields to values to the block, one accumulator and one
value from the sequence.  If you invoke inject without arguments (like
above) the accumulator is initialized with the first element.  After that
the accumulator is updated with every result of the block invocation.

Examples of inject:

# sum of all elements
a.inject{|a,b| a+b}

# product of all elements
a.inject{|a,b| a*b}

# product of all elements
a.inject{|a,b| a*b}

# count elems in a collection
a.inject(0){|cnt,e| cnt + 1}

# count occurrences of a certain element
a.inject(0){|cnt,e| "foo" == e ? cnt + 1 : cnt}

# get the first non nil, non false element
a.inject(nil){|found,e|found || e}

# get the last non nil element
a.inject(nil){|found,e|e.nil? ? found : e}

# convert any enumeration into an array
a.inject([]){|ar,e|ar << e}

You get the picture.  It's quite powerful.

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

I really wouldn't call it "mod" since that makes users expect to calculate
the equivalent of "a % b", which it doesn't.

> 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

You don't need to sort.

> 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]
> ===========

Kind of a more complicated version of inject.  But why do you store the
results in an array?  You just need one value:

gcd = a.shift
a.each{|n|gcd=mod(gcd, n)}
puts gcd

Kind regards

    robert