Prog for g.c.d. of 2 integers

ruby-talk
1

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.

2

“Van Jacques” vanjac12@yahoo.com schrieb im Newsbeitrag
news:70ae81fd.0312110524.309e73c0@posting.google.com…

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
3

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

4

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

5

[snip gcd]

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

Nice collection of math routines.

BTW: Why are extmath not registered on RAA ?

···

On Fri, 12 Dec 2003 07:19:18 +0900, Josef ‘Jupp’ SCHUGT wrote:

–
Simon Strandgaard

6

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

···

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

7

Peter Peter.Vanbroekhoven@cs.kuleuven.ac.be wrote in message news:Pine.LNX.4.44.0312112024020.11559-100000@merlin.cs.kuleuven.ac.be…

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.

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.

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

Van

8

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

9

Florian Pflug writes

a,b=b,a%b while (b != 0)
a.abs

This works well, and either a or b (or both) can be < 0.
I note that a%b < 0 if b < 0, but it’s still OK.
g.c.d. are postive though, so a.abs is the g.c.d.
after the while statement has executed.

My text says that a > b, but (I think) that is so that
the Euclidean algorithm, r_i = r_(i-2) % r_(i-1), for
i >=2, can include a = r_0 and b = r_1 and then say that
r_0 > r_1 > … > r_n > 0 must terminate with the g.c.d r_n.
(r_n | r_(n-1) or r_(n-1) % r_n = 0.)

Josef ‘Jupp’ SCHUGT writes;

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.

This is a good point. In a ruby tutorial by Camerra (sp?),
his example of an addressbook is a good non-math example.

As a physicisct and amateur mathematician I have done many
math programs, whence comes my prejudice.
I will probably continue to do these kinds of problems,
since they help me learn abstract algebra, groups, and
number theory, but I will try to think up some other kinds
of problems, like the addressbook. (Or the song player I
saw somewhere.)

Both your solutions look fine to me.

m / gcd(m, n) * n – I assume, as in C, equal precedence ops.

are left associative. I would write

m*n/gcd(m,n) .

Van

10

I have just submitted our conversation as a feature-request:
http://rubyforge.org/tracker/index.php?func=detail&aid=196&group_id=5&atid=104

···

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.

–
Simon Strandgaard

11

“Van Jacques” vanjac12@yahoo.com schrieb im Newsbeitrag
news:70ae81fd.0312111642.26511e58@posting.google.com…

Peter Peter.Vanbroekhoven@cs.kuleuven.ac.be wrote in message
news:Pine.LNX.4.44.0312112024020.11559-100000@merlin.cs.kuleuven.ac.be…

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
12

“Robert Klemme” bob.news@gmx.net wrote in message news:brcjq4$1ti1d$1@ID-52924.news.uni-berlin.de…

“Van Jacques” vanjac12@yahoo.com schrieb im Newsbeitrag
news:70ae81fd.0312111642.26511e58@posting.google.com…

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

Yes, mod is not a good name. I was going to change it to gcd but never did.

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.

Yes. I don’t know what I was thinking of.

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

Again, good point. I should “finish” my programs better. I developed some bad
and sloppy habits since I wrote a lot of Fortran programs for research that I was
the only one to read. I used a lot of arrays, and here I use them when they aren’t
required.

The last 3 lines of your code

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

look like a good way to get the gcd of an arbitrary
number of numbers. (with mod(x,y) → gcd1(x,y), say).

Van

13

“Van Jacques” vanjac12@yahoo.com schrieb im Newsbeitrag
news:70ae81fd.0312141001.40628225@posting.google.com…

“Robert Klemme” bob.news@gmx.net wrote in message
news:brcjq4$1ti1d$1@ID-52924.news.uni-berlin.de…

“Van Jacques” vanjac12@yahoo.com schrieb im Newsbeitrag
news:70ae81fd.0312111642.26511e58@posting.google.com…

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

Yes, mod is not a good name. I was going to change it to gcd but never
did.

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.

Yes. I don’t know what I was thinking of.

Maybe you were thinking of some kind of shortcut if the smallest value is
1.

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

Again, good point. I should “finish” my programs better. I developed
some bad
and sloppy habits since I wrote a lot of Fortran programs for research
that I was
the only one to read. I used a lot of arrays, and here I use them when
they aren’t
required.

The last 3 lines of your code

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

look like a good way to get the gcd of an arbitrary
number of numbers. (with mod(x,y) → gcd1(x,y), say).

That’s exactly the same what inject does:

gcd = a.inject {|a,b|mod(a,b)}

:slight_smile:

robert