Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   prog for g.c.d. of 2 integers (http://www.velocityreviews.com/forums/t812537-prog-for-g-c-d-of-2-integers.html)

 Van Jacques 12-11-2003 01:24 PM

prog for g.c.d. of 2 integers

Topics from mathematics make good practice programs, IMO.

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

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.

 Robert Klemme 12-11-2003 03:41 PM

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

"Van Jacques" <vanjac12@yahoo.com> schrieb im Newsbeitrag
> Topics from mathematics make good practice programs, IMO.
>
> 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
>
> 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

 Josef 'Jupp' SCHUGT 12-11-2003 10:19 PM

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

Hi!

* Van Jacques; 2003-12-11, 14:14 UTC:
> Topics from mathematics make good practice programs, IMO.

I don't agree with that. When starting with mathematics the most
of the problem in an abstract way.

My implementations are these:

def Extmath.gcd(m, n)
m = Integer(m)
n = Integer(n)
if m <= 0 || n <= 0
return nil
end
loop {
if m < n
m, n = n, m
end
if (l = m % n) == 0
break
end
m = l
}
n
end

def Extmath.lcm(m, n)
m = Integer(m)
n = Integer(n)
if m <= 0 || n <= 0
return nil
end
m / gcd(m, n) * n
end

They are part of extmath - http://extmath.rubyforge.org/

Josef 'Jupp' SCHUGT
--
http://oss.erdfunkstelle.de/ruby/ - German comp.lang.ruby-FAQ
http://rubyforge.org/users/jupp/ - Ruby projects at Rubyforge

 Simon Strandgaard 12-11-2003 10:30 PM

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

On Fri, 12 Dec 2003 07:19:18 +0900, Josef 'Jupp' SCHUGT wrote:
[snip gcd]
> They are part of extmath - http://extmath.rubyforge.org/

Nice collection of math routines.

BTW: Why are extmath not registered on RAA ?

--
Simon Strandgaard

 fgp@phlo.org 12-12-2003 03:56 AM

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

On Fri, Dec 12, 2003 at 12:42:10AM +0900, Robert Klemme wrote:
> 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

Hi

A few remarks about the above - it's late, and i am tired, so forgive me if
I am wrong.. ;-=

.) Since b,a % b = b,a for b > a, you don't need the a,b-swapping I believe:
gdc2(4,6) -> a=4,b=6
a,b = b,a%b -> a=6,b=4%6=4
So the swapping happens automagically.
.) Mathematically speaking, gdc is well-defined for negative arguments too..

So I would write it:
def gcd2(a,b)
a,b=b,a%b while (b != 0)
a.abs
end

greetings, Florian Pflug

 Josef 'Jupp' SCHUGT 12-12-2003 01:48 PM

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

Hi!

* Simon Strandgaard; 2003-12-12, 00:32 UTC:
> On Fri, 12 Dec 2003 07:19:18 +0900, Josef 'Jupp' SCHUGT wrote:
> Nice collection of math routines.
>
> BTW: Why are extmath not registered on RAA ?

I don't want to manually update two locations. Chances are good that
information runs out of sync. I am quit confident that auto-sync of RAA
and Rubyforge is only a question of time.

Josef 'Jupp' SCHUGT
--
http://oss.erdfunkstelle.de/ruby/ - German comp.lang.ruby-FAQ
http://rubyforge.org/users/jupp/ - Ruby projects at Rubyforge

 Simon Strandgaard 12-12-2003 02:19 PM

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

On Fri, 12 Dec 2003 22:48:39 +0900, Josef 'Jupp' SCHUGT wrote:

> Hi!
>
> * Simon Strandgaard; 2003-12-12, 00:32 UTC:
>> On Fri, 12 Dec 2003 07:19:18 +0900, Josef 'Jupp' SCHUGT wrote:
>> Nice collection of math routines.
>>
>> BTW: Why are extmath not registered on RAA ?

>
> I don't want to manually update two locations. Chances are good that
> information runs out of sync. I am quit confident that auto-sync of RAA
> and Rubyforge is only a question of time.

I have just submitted our conversation as a feature-request:
http://rubyforge.org/tracker/index.p..._id=5&atid=104

--
Simon Strandgaard

 All times are GMT. The time now is 04:52 AM.