prog for g.c.d. of 2 integers

V

Van Jacques

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

Robert Klemme

Van Jacques said:
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
Click to expand...

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.
Click to expand...

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
 
J

Josef 'Jupp' SCHUGT

Hi!

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

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.
Click to expand...

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
 
F

fgp

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
Click to expand...
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
 
J

Josef 'Jupp' SCHUGT

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 ?
Click to expand...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

I HAVE MADE AN IMPROVED INPUT FOR INTEGERS ONLY 3
Programming math challenge gives wrong answer 2
How works with large integers ? 0
Need Help: Program to Accept 2 Matrices and Show their Sum 0
Q for a source code in an exercise 1
Calculate rang and derang of ordering of subsets 0
Graph of quadratic function with CanvasRenderingContext2D 2
Function is not worked in C 2

Staff online

Members online

Total: 2,745 (members: 1, guests: 2,744)
Robots: 171

Forum statistics

Threads
474,141
Messages
2,570,817
Members
47,361
Latest member
eitamoro

Latest Threads

Top