## 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 divisorDIM AS INTEGER a,b,c,d,e,f,g,k,lCLSINPUT "How many numbers? (2,3,4...) = ";gDIM z(g) AS INTEGERCLSFOR k = 0 TO g - 1    PRINT "Number ";k + 1;:INPUT " = ";l    z(k) = lNEXT kb = 0FOR a = 0 TO g-1    IF z(a) > b THEN b = z(a)NEXT ae= 0FOR 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 IFNEXT cPRINTPRINT "G.C.D. = ";fSLEEPEND`
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 functionend 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 Functionfunction 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 retend functiondim 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 _    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 functionend namespacedim 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 scopesleep()`
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 divisorDIM AS INTEGER a,b,c,d,e,f,g,k,lCLSINPUT "How many numbers? (2,3,4...) = ";gDIM z(g) AS INTEGERCLSb = 999999999FOR k = 0 TO g - 1    PRINT "Number ";k + 1;:INPUT " = ";l    z(k) = l    IF z(k) < b THEN b = z(k)NEXT ke= 1 '<<< Now, is OkFOR 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 IFNEXT cIF f = 0 THEN f = 1 '<<<<< I think that with this line (modification), it solves the error of result = "0" >>> "1"PRINTPRINT "G.C.D. = ";fSLEEPEND`

Sorry

Return to “General”

### Who is online

Users browsing this forum: No registered users and 7 guests