Velocity Reviews > Ruby > prog for g.c.d. of 2 integers

# prog for g.c.d. of 2 integers

Van Jacques
Guest
Posts: n/a

 12-11-2003
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
Guest
Posts: n/a

 12-11-2003

"Van Jacques" <(E-Mail Removed)> schrieb im Newsbeitrag
news:(E-Mail Removed) om...
> 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
Guest
Posts: n/a

 12-11-2003
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
Guest
Posts: n/a

 12-11-2003
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
Guest
Posts: n/a

 12-12-2003
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
Guest
Posts: n/a

 12-12-2003
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
Guest
Posts: n/a

 12-12-2003
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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post andoni.oconchubhair@ie.fid-intl.com Java 1 10-22-2006 10:43 PM bernd wegener Perl 3 09-22-2004 06:32 PM NetSaver Cisco 0 08-06-2004 02:49 AM John Bailo ASP .Net 1 04-15-2004 09:08 PM Nishi Bhonsle Java 1 01-06-2004 07:50 PM