Program to calculate the GCD of more than two numbers

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

Program to calculate the GCD of more than two numbers

Post by lrcvs »

'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
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Post by paul doe »

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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

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

Post by dodicat »

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
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Post by paul doe »

@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
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Post by paul doe »

@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 _
    GCD overload( _
      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: 578
Joined: Mar 06, 2008 19:27
Location: Spain

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

Post by lrcvs »

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: 578
Joined: Mar 06, 2008 19:27
Location: Spain

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

Post by lrcvs »

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
Post Reply