Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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.
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.
 
Reply With Quote
 
 
 
 
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.
> 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 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

 
Reply With Quote
 
 
 
 
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
important task of programming has already taken place: The modelling
of the problem in an abstract way.

> Comments are welcome.


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


 
Reply With Quote
 
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
 
Reply With Quote
 
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

 
Reply With Quote
 
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


 
Reply With Quote
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Starting and stopping a prog. from another prog. andoni.oconchubhair@ie.fid-intl.com Java 1 10-22-2006 10:43 PM
Piping ping into perl-prog bernd wegener Perl 3 09-22-2004 06:32 PM
NetSaver : Cisco Router Configuration Archiver for windows (alpha stage prog.) NetSaver Cisco 0 08-06-2004 02:49 AM
Prog ID not found on MSSOAP John Bailo ASP .Net 1 04-15-2004 09:08 PM
beans and C code in java prog. Nishi Bhonsle Java 1 01-06-2004 07:50 PM



Advertisments