## Program to calculate the GCD of more than two numbers

General FreeBASIC programming questions.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Program to calculate the GCD of more than two numbers

'Program to find only the greatest common divisor of more than two numbers
(Only for relatively small numbers)
'Examples:
'3567-370968 = 3567
'720-2600 = 40
'4680-7200-16200 = 360

Code: Select all

'Program to find only the greatest common divisor

DIM AS INTEGER a,b,c,d,e,f,g,k,l
CLS
INPUT "How many numbers? (2,3,4...) = ";g
DIM z(g) AS INTEGER
CLS
FOR k = 0 TO g - 1
PRINT "Number ";k + 1;:INPUT " = ";l
z(k) = l
NEXT k
b = 0
FOR a = 0 TO g-1
IF z(a) > b THEN b = z(a)
NEXT a
e= 0
FOR c = 1 TO b
FOR d = 0 TO g - 1
IF z(d) MOD c = 0 THEN
e = e + 1
ELSE e = e -1
END IF
NEXT d
IF e = g THEN
f = c
ELSE
e = 0
END IF
NEXT c
PRINT
PRINT "G.C.D. = ";f
SLEEP
END
paul doe
Posts: 1374
Joined: Jul 25, 2017 17:22
Location: Argentina

### Re: Program to calculate the GCD of more than two numbers

Really nice. This is the same algorithm but wrapped in functions for convenience:

Code: Select all

namespace Math
/'
Returns the greatest from an array of numbers
'/
function _
maxOf( _
numbers() as integer ) _
as integer

dim as integer _
mx => 0

for _
i as integer => lbound( numbers ) _
to ubound( numbers )

mx => iif( numbers( i ) > mx, numbers( i ), mx )
next

return( mx )
end function

/'
Returns the Greatest Common Divisor from an array of integer
numbers.
'/
function _
GCD( _
numbers() as integer ) _
as integer

dim as integer _
count => ( ubound( numbers ) - lbound( numbers ) ) + 1, _
maximum => maxOf( numbers() ), _
result => 0, _
cd => 0

for _
i as integer => 1 _
to maximum

for _
j as integer => lbound( numbers ) _
to ubound( numbers )

cd => iif( numbers( j ) mod i = 0, _
cd + 1, cd - 1 )
next

if( cd = count ) then
result = i
else
cd = 0
end if
next

return( result )
end function
end namespace

/'
Test
'/
dim as integer _
numbers( ... ) => { _
4680, 7200, 16200 }

? Math.GCD( numbers() )

sleep()

Might come in handy. Thanks for sharing.
dodicat
Posts: 6883
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Program to calculate the GCD of more than two numbers

Thanks lrcvs, paul doe.
Here was mine.

Code: Select all

Function HCFpair(a As ulongint, b As ulongint) As ulongint
If b=0 Then Return a Else Return HCFpair(b,a Mod b)
End Function

function hcf(a() as ulongint) as ulongint
dim as ulongint start=a(lbound(a)),ret
for n as long=lbound(a) to ubound(a)
ret=HCFPair(start,a(n))
start=ret
next n
return ret
end function

dim as ulongint n(...)={1616000,20200000,2020000000,12120,1240280,56560,197960,246440}

print  hcf(n())

dim as ulongint m(...)={4680,7200,16200}
print hcf(m())
sleep

paul doe
Posts: 1374
Joined: Jul 25, 2017 17:22
Location: Argentina

### Re: Program to calculate the GCD of more than two numbers

@dodicat: indeed, the recursive approach is the faster of the ones I tested. I tried the 'most efficient' approach here, for example, and for large numbers it just bogs down to a grinding halt. Thanks for sharing.
paul doe
Posts: 1374
Joined: Jul 25, 2017 17:22
Location: Argentina

### Re: Program to calculate the GCD of more than two numbers

@lrcvs: just in case you wanted to know how much of a difference tail recursion makes, here's a simple benchmark for the above. I'm using my implementation (which is similar to dodicat's; the GCD_bf() function is simply your code refactored into a function) but with his test sample:

Code: Select all

namespace Math
/'
Returns the greatest from an array of numbers
'/
function _
maxOf( _
numbers() as integer ) _
as integer

dim as integer _
mx => 0

for _
i as integer => lbound( numbers ) _
to ubound( numbers )

mx => iif( numbers( i ) > mx, numbers( i ), mx )
next

return( mx )
end function

/'
Returns the Greatest Common Divisor from two numbers.
Tail recursive.
'/
function _
byval a as integer, _
byval b as integer ) _
as integer

return( iif( b = 0, a, GCD( b, a mod b ) ) )
end function

/'
Returns the Greatest Common Divisor for an array of numbers.
'/
function _
GCD( _
numbers() as integer ) _
as integer

dim as integer _
start => numbers( lbound( numbers ) ), _
result => 0

for _
i as integer => lbound( numbers ) _
to ubound( numbers )

result => GCD( start, numbers( i ) )
start => result
next

return( result )
end function

/'
Returns the Greatest Common Divisor from an array of integer
numbers. Uses brute-force method.
'/
function _
GCD_bf( _
numbers() as integer ) _
as integer

dim as integer _
count => ( ubound( numbers ) - lbound( numbers ) ) + 1, _
maximum => maxOf( numbers() ), _
result => 0, _
cd => 0

for _
i as integer => 1 _
to maximum

for _
j as integer => lbound( numbers ) _
to ubound( numbers )

cd => iif( numbers( j ) mod i = 0, _
cd + 1, cd - 1 )
next

if( cd = count ) then
result = i
else
cd = 0
end if
next

return( result )
end function
end namespace

dim as integer _
numbers( ... ) => { _
1616000, 20200000, 2020000000, 12120, 1240280, 56560, 197960, 246440 }

? "Using brute-force method: "
scope
dim as integer _
gcd
dim as double _
t => timer()

gcd => Math.GCD_bf( numbers() )

t => timer() - t

? gcd
? "Took: " & t & " seconds."
end scope

?

? "Using tail recursion: "
scope
dim as integer _
gcd
dim as double _
t => timer()

gcd => Math.GCD( numbers() )

t => timer() - t

? gcd
? "Took: " & t & " seconds."
end scope

sleep()
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Program to calculate the GCD of more than two numbers

Hi, all:

It had been a while since I programmed and yesterday a child asked me how to solve a GCD with more than 2 numbers.
I got inspiration from that little program, I did it and it worked.
Search Rosetta Code and the Freebasic forum to see if there was something similar and I couldn't find it.
I thought it was a good idea to upload it in case someone else might be needed.

@dodicat: Hi, as always simple and superior, thanks.

@paul doe: Hi, thank you very much for your program, it is very interesting but I have to study it, I need a little time.

Regards
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Program to calculate the GCD of more than two numbers

Hi, all:

DANGER !!!

MY PROGRAM HAS AN ERROR !!!

The variable: "e = 0" <<<< ERROR !!!

It should say: "e = 1" <<< OK!

Example error:
How many numbers = 5
Numbers: 8888888 - 444444 - 22222 - 4422 - 88
Show: "1" <<< ERROR !!!
It should show: "2" <<< Ok!

This is the corrected program and ("works fine")

Code: Select all

'Program to find only the greatest common divisor
DIM AS INTEGER a,b,c,d,e,f,g,k,l
CLS
INPUT "How many numbers? (2,3,4...) = ";g
DIM z(g) AS INTEGER
CLS
b = 999999999
FOR k = 0 TO g - 1
PRINT "Number ";k + 1;:INPUT " = ";l
z(k) = l
IF z(k) < b THEN b = z(k)
NEXT k
e= 1 '<<< Now, is Ok
FOR c = 1 TO b
FOR d = 0 TO g - 1
IF z(d) MOD c = 0 THEN
e = e + 1
ELSE e = e -1
END IF
NEXT d
IF e = g THEN
f = c
ELSE
e = 0
END IF
NEXT c
IF f = 0 THEN f = 1 '<<<<< I think that with this line (modification), it solves the error of result = "0" >>> "1"
PRINT
PRINT "G.C.D. = ";f
SLEEP
END

Sorry