Click here to Skip to main content
13,798,414 members
Rate this:
 
Please Sign up or sign in to vote.
See more:

Greatest Common Denominator


Today's challenge, sent in by Bob Hent, is an oldie and a goodie.

Given a list of integers of the form: (n0, n1, n2, … nx)
Where (0 < n ≤ 10000) and (x < 500)
Return the Greatest Common Divisor (GCD), where GCD is defined as the largest positive integer that divides all the numbers without a remainder.

Example:

Given: [247, 8645, 1216, 3648]
Return: 19
Because: 247/19 = 13, 8645/19 = 455, 1216/19 = 64, 3648/19 = 192

The prize is a CodeProject mug. Points for the most unexpected code. Cutting and pasting from the interwebz will get you a solution, but no points. Stretch your mind a little.

What I have tried:

To remain sane.

Last week's winner is from Fraser Duthie[^], though special mentions go to ProgramFox (for nastiest) and H2O-au (for neatest).

Send in your ideas for next week, and don't forget to vote on the entries that are posted!
Posted 9-Dec-16 3:09am
Updated 15-Dec-16 20:06pm
v3
Comments
PIEBALDconsult 9-Dec-16 13:45pm
   
"Points for the most unexpected code"

I might need to create a language named "Spanish Inquisition".
Graeme_Grant 9-Dec-16 16:45pm
   
"don't forget to vote on the entries that are posted!"
PIEBALDconsult 9-Dec-16 17:42pm
   
Homey don't play dat.
Jon McKee 11-Dec-16 2:30am
   
I love that there are no votes on any solution =D Everyone thinks their solution is the best (I'm no exception).
Graeme_Grant 11-Dec-16 2:43am
   
Either that or no one else other than the people submitting solutions are looking at them...
Jon McKee 11-Dec-16 2:48am
   
Very true. Would probably improve if the challenge is cross-posted in the Lounge like the first one.
PIEBALDconsult 11-Dec-16 11:06am
   
I try not to vote for or against myself.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 6

Caching prime factors

What strikes me as interesting about this problem is the low value of nmax = 10,000.
* There are only 1,229 prime numbers less than 10,000 (the largest of which is 9,973)
* All integers less than 10,000 have at most 13 prime factors (since 214 = 16,384 > 10,000)

So what if we took some time up-front to cache the prime factors of every possible input integer?

The math: each number (n) is a product of all primes less than itself (pi), each raised to some power (ai). The GCD is the set of minimum powers across all test numbers

The largest possible number of prime factors (largest value of ai) would be 13 - so we can cache these powers as bytes. A full 10,000 x 1,229 2D array of bytes is 95.1 MB, which is probably not unreasonable.

BUT, this 2D array consists mostly of zeroes (at least 1,216 powers out of 1,229 are zero), so using an array of key-value pairs shrinks this to ~1.2 MB. Compressing the array in this way will also have speed benefits.

Our cache will contain the set of primes less than nmax, and an array of dictionaries, one for each integer less than nmax, that connects each prime (indexed by ushort) with a power (stored as byte).

Now the code... (Sorry it's not the tidiest but it'll have to do for now.)

using PrimeFactorCollection = Dictionary<ushort, byte>;

public class CachedGcdFetcher
{
    const int MaxAllowableMaxAllowableValue = 821640;
    const double ATinyBitMoreToBeOnTheSafeSide = 1e-6;

    public int MaxAllowableValue { get; private set; }

    int[] primes;
    PrimeFactorCollection[] primeFactorCache;

    ...

}

Note that the MaxAllowableValue (nmax = 10,000) has an upper limit. Since we're using a ushort when indexing the primes to conserve RAM, we can only handle 65,535 primes. So nmax < 65,536th prime (821,641).

The cache itself is the two fields int[] primes and PrimeFactorCollection[] primeFactorCache.

Next, some helper functions.

static bool isPrime(int x)
{
    var maxPossibleFactor = (int)Math.Floor(Math.Sqrt(x)
        + ATinyBitMoreToBeOnTheSafeSide);

    return !Enumerable.Range(2, maxPossibleFactor)
        .Any(a => x % a == 0);
}

int pfCollectionToNumber(PrimeFactorCollection c)
{
    var output = 1;
    foreach (var f in c)
    {
        var p_i = primes[f.Key];
        for (int a_i = 0; a_i < f.Value; a_i++)
        {
            output *= p_i;
            if (output > MaxAllowableValue)
                return output;
        }
    }
    Console.WriteLine(output);
    return output;
}

PrimeFactorCollection indicesToPfCollection(IEnumerable<ushort> pfIndices)
{
    var a = new PrimeFactorCollection();
    foreach (var ig in pfIndices.GroupBy(i => i))
        a.Add(ig.Key, (byte)ig.Count());
    return a;
}

The cache is built in the constructor, and the GCD is fetched in int GetGcd(int[] ints).

public CachedGcdFetcher(int maxAllowableValue)
{
    // Valiate parameter
    if (maxAllowableValue < 2 || MaxAllowableValue >= MaxAllowableMaxAllowableValue)
        throw new ArgumentOutOfRangeException(
            nameof(maxAllowableValue),
            maxAllowableValue,
            "This class can only handle numbers in the range [2, " 
                + MaxAllowableMaxAllowableValue + "].");

    // Initialise properties
    this.MaxAllowableValue = maxAllowableValue;
            
    // Build a cache of primes
    primes = Enumerable.Range(2, MaxAllowableValue)
        .Where(isPrime)
        .ToArray();
            
    // Build a cache of prime factors by checking prime divisibilities
    primeFactorCache = new PrimeFactorCollection[MaxAllowableValue + 1];
    for (int n = 2; n < primeFactorCache.Length; n++)
    {
        // Keep a list of prime factors with non-zero powers
        var pfs = new List<KeyValuePair<ushort, byte>>();

        for (ushort i = 0; i < primes.Length; i++)
        {
            var nr = n;
            var p_i = primes[i];
            byte a = 0;
            while (nr % p_i == 0)
            {
                a++;
                nr /= p_i;
            }
            if (a > 0)
                pfs.Add(new KeyValuePair<ushort, byte>(i, a));
        }

        // Transfer the prime factors to a dictionary (with known capacity)
        var pfs2 = new PrimeFactorCollection(pfs.Count);
        foreach (var pf in pfs)
            pfs2.Add(pf.Key, pf.Value);

        primeFactorCache[n] = pfs2;
    }
}

public int GetGcd(int[] ints)
{
    // We are reliant on good data, so validate
    foreach (var n in ints)
        if (n < 2 || n > MaxAllowableValue)
            throw new ArgumentOutOfRangeException(
                nameof(ints),
                "All values of input array should be in range [2, "
                    + n + "]");

    // Lookup cache for each input n, and collect all prime factors
    var indices = new List<ushort>();
    foreach (var n in ints)
        foreach (var f in primeFactorCache[n])
            if (!indices.Contains(f.Key))
                indices.Add(f.Key);

    // Set up output prime factor collection
    var outputFactors = new PrimeFactorCollection();
    foreach (var i in indices)
        outputFactors.Add(i, byte.MaxValue);

    // Find minimum powers
    foreach (var i in indices)
    foreach (var n in ints)
    {
        var c = primeFactorCache[n];
        if (!c.ContainsKey(i))
            // if not in collection, it's a zero
            outputFactors[i] = 0;
        else
            // if in collection, take the smallest
            outputFactors[i] = Math.Min(outputFactors[i], c[i]);
    }

    // Build GCD
    return pfCollectionToNumber(outputFactors);
}

Standard disclaimer: this isn't thoroughly tested beyond the example (it said 19! Yay!). I did a quick check of memory usage (~1.2 MB) and speed (cache builds in ~170 ms). I have no idea if this actually provides a performance benefit vs. other methods. I might do some performance tests against other algorithms later...
  Permalink  
v2
Comments
PIEBALDconsult 10-Dec-16 11:02am
   
Don't you need the primes only up to the square root of Nmax (or half)?
Jon McKee 10-Dec-16 11:58am
   
Definitely have me beat on memory usage (21 MB), but I've got ya on speed. I haven't posted it because there's no point but I modified my algorithm to use uint to double the number range. I can run 1,000,000 numbers in the range 0 <= n <= 4,285,200,000 in ~155 ms =)
PIEBALDconsult 10-Dec-16 12:50pm
   
As for caching, why not add numbers and their prime factors only as they're encountered in the input?
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 7

I do have implementations of GCD using the Euclid and binary algorithms -- for two operands only -- but I chose not to use them.
So here's a simple (sophomoric perhaps) method that will reduce the values in the List and return the GCD.

It works for negative values, zeroes, and single-item input lists.

Factor should be a List of prime numbers in ascending order, with enough range to factor the input value of least magnitude (closest to zero).

public static int
Reduce
(
  System.Collections.Generic.IList<int> List
,
  System.Collections.Generic.IList<int> Factor
)
{
  /* Add checks for null and empty as desired. */

  int result = 1 ;

  int least = System.Math.Abs ( List [ 0 ] ) ;

  for ( int i = 1 ; i < List.Count ; i++ )
  {
    if ( least > System.Math.Abs ( List [ i ] ) )
    {
      least = System.Math.Abs ( List [ i ] ) ;
    }
  }

  int f = 0 ;

  while ( ( f < Factor.Count ) && ( least >= Factor [ f ] ) )
  {
    int i = 0 ;

    while ( ( i < List.Count ) && ( List [ i ] % Factor [ f ] == 0 ) )
    {
      i++ ;
    }

    if ( i == List.Count )
    {
      result *= Factor [ f ] ;

      least /= Factor [ f ] ;

      for ( i = 0 ; i < List.Count ; i++ )
      {
        List [ i ] /= Factor [ f ] ;
      }
    }
    else
    {
      f++ ;
    }
  }

  return ( result ) ;
}


For testing convenience; here's a List of the first one hundred prime numbers:

Primes = ( new System.Collections.Generic.List<int>
( new int[]
{
    2 ,   3 ,   5 ,   7 ,  11 ,  13 ,  17 ,  19 ,  23 ,  29 ,
   31 ,  37 ,  41 ,  43 ,  47 ,  53 ,  59 ,  61 ,  67 ,  71 ,
   73 ,  79 ,  83 ,  89 ,  97 , 101 , 103 , 107 , 109 , 113 ,
  127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 ,
  179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 ,
  233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 ,
  283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 ,
  353 , 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 ,
  419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , 461 , 463 ,
  467 , 479 , 487 , 491 , 499 , 503 , 509 , 521 , 523 , 541
} ) ).AsReadOnly() ;
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 9

This is the algorithm of solution 2, improved by means of PIEBALD's suggestions, and ported to C# in order to simplify the comparison with other algorithms.
In my humble opinion ( :-D ) it is remarkably fast.

static uint gcd(uint[] a)
{ 
  uint iom = 0;
  uint min;
  uint i;
  uint len = (uint)a.Length;

  // find index of minimum (iom)  
  for (i = 1; i < len; ++i)
    if (a[iom] > a[i]) iom = i; 
  
  // move minimum to a[0]
  min = a[iom];
  a[iom] = a[0];
  a[0] = min;
	
  while ( len > 1)
  {
    if (a[0] == 1) return 1;
    len = reminders(a, len);
  }
   return a[0];
}

static uint reminders(uint [] a, uint len)
{
  // find the reminders, at the same time find new minimum and remove zeroes
  uint iom = 0;
  uint i=1;
  while (i<len)
  {
    a[i] %= a[0];
    if (a[i] == 0)
    {
      a[i] = a[len-1];
      --len;
    }
    else
    {
      if (a[i] < a[iom])
        iom = i;
      ++i;
    }
  }
  if (iom>0)
  { // move min to a[0]
    uint tmp = a[0];
    a[0] = a[iom];
    a[iom] = tmp;
  }
  return len;
}
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 10

Well... Many of you knows that i'm a fan of Linq solutions!

//given list
int[] givenlist = new int[]{247, 8645, 1216, 3648};
//int[] givenlist = new int[]{5, 12, 316, 648}; //gcd: 1

//get the list of divisors from 1 to min of given list
//gcd cannot be greater then min of given list
int[] divisors = Enumerable.Range(1, givenlist.Min()).ToArray();
//all numbers from given list divide by all dividors

//cross join: numbers and divisors
//get only those numbers with 0 as remainder
//group data by divisor
//get a list of common divisors (at least there must be only 1)
//get GCD
var gcd = divisors
	.SelectMany(gl=> givenlist, (di, gl) => new {divisor=di, number=gl})
	.Where(a=>a.number % a.divisor==0)
	.GroupBy(x=> x.divisor)
	.Where(grp=>grp.Count()==givenlist.Length)
	.Max(a=>a.Key);


Note: above code executes in less than 0.001 sec.

I hope, my unconventional way to find a GCD will arouse your interest.
  Permalink  
v2
Comments
Chris Maunder 13-Dec-16 19:30pm
   
That's so awful it's awesome! +1
Maciej Los 14-Dec-16 3:33am
   
Thank you, Chris.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 11

Finally I got to finish the 6502 assembly solution... I used a C64 emulator as a host for the code, so beside the actual computation, there are some lines to print the result out too...

The most interesting thing are, that not only 6502 is a 8 bit CPU (so not 16 bit arithmetic), but it has no built in multiplication or division. So I had to handle 16 bit subtraction and create 16 bit multiplication... Except that, it is an implementation of the binary solution...

First of all, here a screenshot of the C64 after the code run: gcd-c64.png (15.7 KB)

For those want to run it, a PRG file to load: gcd.zip (.6 KB) (zipped, so I can upload it)

Here the assembly code written in C64Studio:
; GREATEST COMMON DENOMINATOR

; HELPERS

; KERNEL CALLS
CHROUT = $FFD2 ; PRINT A CHAR

; BASIC CALLS
N2A = $BDCD ; PRINT A NUMBER
STROUT = $AB1E ; PRINT ZERO TERMINATED STRING

; MACRO
!MACRO PRINT_MSG ADDR {
  PHA
  TXA
  PHA
  TYA
  PHA
  
  LDA #<ADDR
  LDY #>ADDR
  JSR STROUT

  PLA
  TAY
  PLA
  TAX
  PLA
}

* = $0801 ; BASIC LOADER
!BYTE $0C,$08,$0A,$00,$9E,$20,$38,$31,$39,$32,$00,$00,$00 ; 10 SYS 8192

*=$2000 ; CODE SEGMENT  
  LDA COUNT
  ASL
  STA LENGTH

  +PRINT_MSG TITLE_MSG
  
  JSR PRINT_DATA
MAIN_LOOP
  LDX COUNT
  STX INDEX
  DEC INDEX
  
  LDX #$00

INNER_LOOP  
  ; CHECK FIRST NUMBER FOR ZERO
  LDY VALUES,X
  CPY #$00
  BNE CHECK2
  LDA VALUES+1,X
  CMP #$00
  BEQ ZERO

  ; CHECK SECOND NUMBER FOR ZERO
CHECK2
  LDY VALUES+2,X
  CPY #$00
  BNE NO_ZERO
  LDA VALUES+3,X
  CMP #$00
  BEQ ZERO
  
  ; BOTH NUMBERS ARE NON-ZERO
NO_ZERO
  LDA VALUES,X
  STA VALUE1
  LDA VALUES+1,X
  STA VALUE1+1

  LDA VALUES+2,X
  STA VALUE2
  LDA VALUES+3,X
  STA VALUE2+1

  JSR GCD2
  
  LDA VALUE1
  STA VALUES,X
  LDA VALUE1+1
  STA VALUES+1,X

  INX
  INX
  
  DEC INDEX
  BNE INNER_LOOP  
  
  DEC COUNT
  LDA COUNT
  CMP #$01
  BNE MAIN_LOOP
  
  +PRINT_MSG ANSWER_MSG

  LDX VALUES
  LDA VALUES+1
  JSR N2A
  
  JMP END
  
ZERO
  +PRINT_MSG NO_ZERO_MSG

END  
  RTS

PRINT_DATA
  PHA
  TXA
  PHA
  TYA
  PHA

  +PRINT_MSG LIST_MSG

  LDY #$00
  
LOOP
  STY INDEX
  LDX VALUES,Y
  LDA VALUES+1,Y
  JSR N2A
  LDA #$2C
  JSR CHROUT
  LDY INDEX
  INY
  INY
  CPY LENGTH
  BNE LOOP

  LDA #$14
  JSR CHROUT
  LDA #$0D
  JSR CHROUT
    
  PLA
  TAY
  PLA
  TAX
  PLA
  
  RTS
  
GCD2
  PHA
  TXA
  PHA
  TYA
  PHA
  
  LDA #$00
  STA POWER

GCD_LOOP
  LDA VALUE1
  CMP VALUE2
  BNE DIFFERENT
  LDA VALUE1+1
  CMP VALUE2+1
  BNE DIFFERENT

  JMP FOUND
  
DIFFERENT
  CLC
  LDA VALUE1
  LSR
  BCS VALUE_ODD
  CLC
  LDA VALUE2
  LSR
  BCS VALUE_ODD
  
  CLC
  LSR VALUE1+1
  ROR VALUE1
  
  CLC
  LSR VALUE2+1
  ROR VALUE2
  
  INC POWER
  JMP GCD_LOOP
  
VALUE_ODD
  CLC
  LDA VALUE1
  LSR
  BCS VALUE1_ODD
  
  CLC
  LSR VALUE1+1
  ROR VALUE1

  JMP GCD_LOOP

VALUE1_ODD
  CLC
  LDA VALUE2
  LSR
  BCS ALL_ODD
  
  CLC
  LSR VALUE2+1
  ROR VALUE2

  JMP GCD_LOOP
  
ALL_ODD
  LDA VALUE1+1
  CMP VALUE2+1
  BCC V1_LT_V2
  BNE V1_GT_V2
  LDA VALUE1
  CMP VALUE2
  BCC V1_LT_V2

V1_GT_V2
  SEC       
  LDA VALUE1
  SBC VALUE2
  STA VALUE1
  LDA VALUE1+1
  SBC VALUE2+1
  STA VALUE1+1
  
  CLC
  LSR VALUE1+1
  ROR VALUE1

  JMP GCD_LOOP

V1_LT_V2
  SEC       
  LDA VALUE2
  SBC VALUE1
  STA VALUE2
  LDA VALUE2+1
  SBC VALUE1+1
  STA VALUE2+1
  
  CLC
  LSR VALUE2+1
  ROR VALUE2

  JMP GCD_LOOP

FOUND
  LDA #$01
COMPUTE_POWER
  LDX POWER
  BEQ COMPUTE_FINAL
  ASL
  DEC POWER
  JMP COMPUTE_POWER
  
COMPUTE_FINAL
  STA POWER
  LDA #$00
  STA TEMP
  STA TEMP+1
  
COMPUTE_LOOP
  CLC
  LDA VALUE1
  ADC TEMP
  STA TEMP
  LDA VALUE1+1
  ADC TEMP+1
  STA TEMP+1
  DEC POWER
  BNE COMPUTE_LOOP
  
  LDA TEMP
  STA VALUE1
  LDA TEMP+1
  STA VALUE1+1
  
  PLA
  TAY
  PLA
  TAX
  PLA
  
  RTS
  
*=$2400 ; DATA SEGMENT
VALUES
  !WORD 247, 8645, 1216, 3648
VALUE1
  !WORD 0
VALUE2
  !WORD 0
TEMP
  !WORD 0
COUNT
  !BYTE 4
INDEX
  !BYTE 0
LENGTH
  !WORD 0
POWER
  !BYTE 0
TITLE_MSG
  !TEXT $81, $93, "       CODEPROJECT CODE CHALLENGE", 13, "        GREATEST COMMON DIVISOR!", $9A, 13, 13, 0
NO_ZERO_MSG
  !TEXT $96, "NAN", $9A, 13, 0
LIST_MSG
  !TEXT $81, "NUMBERS:", $9A, 13, "  ", 0
ANSWER_MSG
  !TEXT $81, "GCD:", $9A, 13, "  ", 0
  Permalink  
v3
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

The algo works roughly this way
  • find the minimum of the list.
  • replace each item of the list (but the minimum) with the reminder of itself divided by the minimum.
  • remove all the zeroes (shrinking the list).

The described steps are repeated until:
  • there is just one item in the list: success, the item is the solution

or
  • minimum is 1: success, 1 is the solution


[fixed after Jon McKee remark]

The code gives a more precise definition:
int index_of_min( int a[], int len)
{
  int index = 0;
  int i;
  for ( i=0; i<len; ++i)
  {
    if (a[index] > a[i])
      index = i;
  }
  return index;
}

int remove_zeroes(int a[], int len)
{
  int i;
  for ( ; len > 0; --len)
    if ( a[len-1] > 0 )  break;

  for (i=0; i<len; ++i)
  {
    if (a[i] == 0)
    {
      a[i] = a[len-1];
      --len;
    }    
  }      
  return len;
}

void reminders(int a[], int len, int index)
{
  int i;
  for (i = 0; i<len; ++i)
  {
    if ( i != index)
      a[i] %= a[index];
  }
}

int gcd( int a[], int len)
{

  while ( len > 1)
  {
    int index = index_of_min(a, len);
    if ( a[index] == 1 )
      return 1;
    reminders(a, len, index);
    len = remove_zeroes(a, len);
  }
  return a[0];
}


With the sample data (247, 8645, 1216, 3648), it obtains the result in four iterations:
247
8645
1216
3648
----
247
190
228
----
57
190
38
----
19
38
----
19
----
result: 19




A complete program, in order to test it:
#include <stdio.h>

void dump( int a[], int len)
{
  int i;
  for (i=0; i<len; ++i)
    printf("%d\n", a[i]);

  printf("----\n");
}

int index_of_min( int a[], int len)
{
  int index = 0;
  int i;
  for ( i=0; i<len; ++i)
  {
    if (a[index] > a[i])
      index = i;
  }
  return index;
}

int remove_zeroes(int a[], int len)
{
  int i;
  for ( ; len > 0; --len)
    if ( a[len-1] > 0 )  break;

  for (i=0; i<len; ++i)
  {
    if (a[i] == 0)
    {
      a[i] = a[len-1];
      --len;
    }
  }      
  return len;
}

void reminders(int a[], int len, int index)
{
  int i; 
  for (i = 0; i<len; ++i)
  {
    if ( i != index)
      a[i] %= a[index];
  }
}

int gcd( int a[], int len)
{

  while ( len > 1)
  { 
    int index = index_of_min(a, len);
    if ( a[index] == 1 )
      return 1;
    reminders(a, len, index);
    len = remove_zeroes(a, len);
    dump(a, len);
  }
  return a[0];
}


int main()
{
  int a[] = {247, 8645, 1216, 3648 };

  int len = sizeof(a) / sizeof(a[0]);

  dump(a, len);

  int result = gcd(a, len);
  if ( result > 0)
    printf("result: %d\n", a[0]);
  else
    printf("no match\n");
  return a[0];
}
  Permalink  
v3
Comments
PIEBALDconsult 9-Dec-16 14:54pm
   
Surely you can perform the tasks of index_of_min and remove_zeroes within reminders.
No need to enumerate the list three times per iteration.
As you calculate the reminders (remainders), keep track of the index of the min, and also swap out zeroes.
CPallini 9-Dec-16 15:45pm
   
Good points. :thumbsup:
Jon McKee 9-Dec-16 18:43pm
   
{ 5, 7, 20, 40 } breaks it and returns 0 instead of 1. The algorithm assumes the list has a common GCD greater than 1 when it may not according to the challenge =) EDIT: Clarified "greater than 1", 1 is a GCD as PIE pointed out =)
CPallini 10-Dec-16 5:12am
   
Well, I just misunderstood the requirements. A return 1; fixed it, thanks.
PIEBALDconsult 10-Dec-16 11:32am
   
Exactly; 1 is a reasonable value for GCD.
Jon McKee 10-Dec-16 11:38am
   
Especially considering the common approach to calculating LCM uses the GCD in the divisor/denominator. 0 would be no bueno.
CPallini 10-Dec-16 16:13pm
   
Well, I know that.
In my blundering mind I assumend it was a requirement (return 0 if no GCD > 1 was found). I read all the revisions of the requirements and can confirm there is no trace of such a costraint. Probably I should stop taking hallucinogens :-D
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

There are a total of three parts in this solution, read them with patience. :zzz:

+++++[Part 1]+++++

This is brute-force search with the algorithm as follows:
1.  GET a list of integers
1.  SET GCD = 1
2.  SET DIVISOR = 2
3.  WHILE DIVISOR <= the smallest integer
    3.1  Divide each integers by the DIVISOR, starting with the smallest integer and proceed in ascending order 
    3.2  IF ALL divisions result in no remainder 
         3.2.1 SET GCD = DIVISOR
    3.3  DIVISOR = DIVISOR + 1
4.  DISPLAY GCD

Then, implement it in plain old JavaScript:
var integers = [247, 8645, 1216, 3648];
var gcd = 1;
var divisor = 2;
while(divisor <= integers[0]){
	var isAllDivisible = true;
	for(i=0;i<integers.length;i++){
    	if(integers[i] % divisor != 0){
            isAllDivisible = false;
        	break;
        }
    }
    if(isAllDivisible){
       	gcd = divisor; // continue to search
    }
    divisor++; 
}
alert(gcd);

Edit fiddle - JSFiddle[^]

+++++[Part 2]+++++

The main deficiency of the above brute-force search algorithm is that it has to exhaust the search from 1 all the way to the smallest integer, even if a number is found to be divisible by all integers along the way.

A better way will be to do the reverse, that is to start the search from the smallest integer and move towards ground zero, in this way, the first number that is found to be divisible by all elements will be the answer and the search can be stopped. This way can potentially reduce the search space and as a result more efficient. The code snippet is shown below:
var integers = [247, 8645, 1216, 3648];
var gcd = divisor = Math.min.apply(Math, integers);
while(divisor > 0){
	var isAllDivisible = true;
	for(i=0;i<integers.length;i++){
    	if(integers[i] % divisor != 0){
          isAllDivisible = false;
          break;
        }
    }
    if(isAllDivisible){
       	gcd = divisor; // GCD found and stop searching
        break;
    }
    divisor--; 
}
alert(gcd);

Edit fiddle - JSFiddle[^]

+++++[Part 3]+++++

This is the last part. How about trying it out using some Stochastic Optimizaton.

Optimization is the process to seek optimal solutions for problems that do not have perceived way to find solutions (of course this GCD thing is not one of them). The process of optimization evolves the optimal solutions by searching for random candidate solutions in a search space, weeding out the weaker but retaining the stronger based on their fitness. The evolution continues until certain terminating criteria are met, such as the perceived optimality of the solutions or number of iterations.

Enough talking, let get back to this GCD question, I have worked out the algorithm as follows:
First things first, set up the necessary parameters:
search space: lowerBound = 1, upperBound = min(integers) = 247
population size p = 10
candidates  = c0,c1, ...c9
number of iteration i = 10
fitness of candidate = max(candidates) 

The actual optimization process:

1.  Randomly picked a population of candidate GCD's lowerBound <= c0,c1, ...c9  <= upperBound 
2.  Divide each integers with each candidate GCD's 
    r0=247/c0, ... r9=247/c9
    r0=8645/c0, ... r9=8645/c9 
    ...and so on
3.  Discard those candidates that produce non-zero remainders.
4.  Assign the candidate that have the best fitness to be the lowerBound of the search space. (This will reduce the search space and lead to eventual convergence to the optimal solution.)
5.  Rejuvenate the population by replacing candidates that are discarded or fall below the lowerBound.
6.  REPEAT step 2 UNTIL the number of iteration is reached.

Translating the whole thing into JS code:
/*
	Stochastic Optimization in Search of Greatest Common Divisor (GCD)
  By Peter Leow the stochastic coder
*/

var integers = [247, 8645, 1216, 3648];

// Setting parameters
var lowerBound = 1;
var upperBound = Math.min(...integers);
var populationSize = 10; // increase this for better chance
var population = [];
var maxIteration = 20; // increase this for better chance

function generatePopulation(population, populationSize, lowerBound, upperBound) {
  for (var i = 1; i < populationSize; i++) {
    population[i] = Math.floor((Math.random() * upperBound) + lowerBound);
  }
  return population;
}

var desc = ""
population[0] = lowerBound;

for (var i = 0; i < maxIteration; i++) {

  desc += "Iteration: " + (i + 1) + "<br>";
  // Randomly generate candidate GCD's within bound
  population = generatePopulation(population, populationSize, lowerBound, upperBound);
  desc += "Candidates at start: " + population + "<br>";
  // Test candidates and weep out the failure
  for (var j = 0; j < population.length; j++) {
    for (var k = 0; k < integers.length; k++) {
      if (integers[k] % population[j] != 0) {
        population.splice(j, 1); // remove failed candidate from the population
        j--;
        break; // and break out!
      }
    }
  }
  desc += "Candidates left: " + population + "<br>";
  // Find the new lower bound of the search space
  if (population.length != 0) {
    lowerBound = Math.max(...population);
    population = [];
    population[0] = lowerBound;
  }
  desc += "Best candidate so far: " + lowerBound + "<br>";
  desc += "====================================" + "<br>";
}

document.getElementById("desc").innerHTML = desc;

And the HTML tag to display the progress and result:
<div id="desc"></div>

Edit fiddle - JSFiddle[^]

Run it, and you may not get the correct answer of 19, run it several times, you should get it. If you increase the number of iteration or the population size, the chances of getting the right answer to the GCD problem also increase. Catch a glimpse of an example of a run for 20 iterations:
Iteration: 1
Candidates at start: 1,213,240,185,219,247,207,216,160,179
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 2
Candidates at start: 1,125,159,51,177,154,134,149,78,64
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 3
Candidates at start: 1,84,153,237,234,52,5,24,43,23
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 4
Candidates at start: 1,9,195,181,46,228,14,84,235,129
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 5
Candidates at start: 1,103,241,72,22,44,30,166,109,203
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 6
Candidates at start: 1,174,4,235,3,205,23,199,190,181
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 7
Candidates at start: 1,53,139,131,180,180,222,128,181,45
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 8
Candidates at start: 1,31,136,55,168,218,101,51,94,48
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 9
Candidates at start: 1,127,133,136,19,121,171,6,96,200
Candidates left: 1,19
Best candidate so far: 19
====================================
Iteration: 10
Candidates at start: 19,65,204,241,222,63,56,116,141,38
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 11
Candidates at start: 19,47,225,41,199,222,226,239,109,209
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 12
Candidates at start: 19,243,32,120,243,25,132,168,191,235
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 13
Candidates at start: 19,218,162,78,170,159,215,137,193,165
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 14
Candidates at start: 19,141,263,247,94,49,216,146,135,181
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 15
Candidates at start: 19,224,128,252,93,48,248,172,110,78
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 16
Candidates at start: 19,48,155,179,258,190,221,142,70,48
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 17
Candidates at start: 19,51,81,231,21,135,219,93,245,124
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 18
Candidates at start: 19,81,102,46,123,166,68,159,203,239
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 19
Candidates at start: 19,203,123,219,44,24,56,200,35,226
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 20
Candidates at start: 19,129,152,22,205,248,174,131,44,121
Candidates left: 19
Best candidate so far: 19
====================================

You have just learned that the solutions provided by optimization may vary. Note that the quality of solutions derived from optimization will depend on many factors, some of which are the population size and the number of iteration.

All roads lead to Rome", while the shorter ones promise efficiency, the longer ones opportunities to enjoy the travel, take in more scenery, and may even lead to new discovery. Why are we always in the hurry?

Um... That gives me a source of inspiration for my next article...
  Permalink  
v21
Comments
F-ES Sitecore 9-Dec-16 9:45am
   
Euclid will be spinning in his grave!
PIEBALDconsult 9-Dec-16 13:13pm
   
Did he have to handle 500 items at once?
Patrice T 9-Dec-16 14:20pm
   
I fear he turned to fan.
Mohibur Rashid 12-Dec-16 16:36pm
   
Enjoyed !
Peter Leow 9-Dec-16 19:27pm
   
He should be happy as long as this serves as the point of contention that spurs more innovative solutions. I can see that it has already happened. Cheer!
PIEBALDconsult 9-Dec-16 13:14pm
   
You might want to try using only prime numbers as divisors.
Patrice T 9-Dec-16 14:21pm
   
Dear Peter,
there are much more efficient algorithms.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 3

Language: Clipper/xHarbour
clear
? "CCCP Code Chalenge Code Project"
? "GCD"
lst= {247, 8645, 1216, 3648}
ans= gcd(lst)
? ans
return

function gcd(lst)
	b= lst[1]
	for scan=2 to len(lst)
		a= lst[scan]
		while (tmp:=a%b) != 0
			a= b
			b= tmp
		enddo
	next
	return b

I tried to be as straight as possible
Take the first 2 numbers and calculate their GCD.
Take the first GCD and third number and calculate their GCD.
And so on until the end.
  Permalink  
v2
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 4

Thanks to Peter Leow[^] for taking the fun out of finding the solution. Whilst he has an interesting solution, I thought that there would be a much faster way of doing it.

I like fast code and whilst I did not invent the "Binary Greatest Common Divisor" algorithm (original C version for 2 values found here...), I have put my own slightly improved C# version below.

using System;
using System.Linq;

namespace GCD
{
    class Program
    {
        static void Main(string[] args)
        {
            var values = new[] { 247, 8645, 0, -1216, 3648 };
            Console.WriteLine("Greatest Common Denominator - Binary version");
            Console.WriteLine("");
            Console.WriteLine($"Given:   {string.Join(", ", (values))}");
            Console.WriteLine($"Returns: {gcd(values)}");
            Console.WriteLine("");
            Console.WriteLine("-- Press any key --");
            Console.ReadKey();
        }

        public static int gcd(int[] x)
        {
            if (x.Length < 2)
                throw new ArgumentException("More than 2 number required.");

            // check for negatives and zero values - as suggested by PIEBALDconsult
            x = x.Where(n => n != 0).Select(n => n < 0 ? -n : n).ToArray();

            int v = gcd(x[x.Length - 1], x[x.Length - 2]);
            for (int i = x.Length - 3; i >= 0; i--)
                v = gcd(v, x[i]);

            return v;
        }

        private static int gcd(int u, int v) 
            => (int) gcd((uint) u, (uint) v);

        private static uint gcd(uint u, uint v)
        {
            int shift;
            if (u == 0) return v;
            if (v == 0) return u;

            shift = ctzb(u | v);
            u >>= ctzb(u);

            do
            {
                v >>= ctzb(v);
                if (u > v) Swap(ref v, ref u);
                v = v - u;
            } while (v != 0);

            return u << shift;
        }

        // Count trailing zero bits
        private static int ctzb(uint x)
        {
            int n = 1;
            if ((x & 0x0000FFFF) == 0)
            {
                n += 16;
                x >>= 16;
            }
            if ((x & 0x000000FF) == 0)
            {
                n += 8;
                x >>= 8;
            }
            if ((x & 0x0000000F) == 0)
            {
                n += 4;
                x >>= 4;
            }
            if ((x & 0x00000003) == 0)
            {
                n += 2;
                x >>= 2;
            }
            return (int) (n - (x & 1));
        }

        public static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp = lhs;
            lhs = rhs;
            rhs = temp;
        }
    }
}


And the output:

Greatest Common Denominator - Binary version

Given:   247, 8645, 0, -1216, 3648
Returns: 19

-- Press any key --


UPDATE: I decided to go back to my roots and create a VB.Net version as well...

Module Module1

    Sub Main()

			Dim values() = { 247, 8645, 0, -1216, 3648 }

			Console.WriteLine("Greatest Common Denominator - Binary version")
			Console.WriteLine("")
			Console.WriteLine($"Given:   {string.Join(", ", (values))}")
			Console.WriteLine($"Returns: {gcd(values)}")
			Console.WriteLine("")
			Console.WriteLine("-- Press any key --")
			Console.ReadKey()

	End Sub

	Public Function gcd(x As Integer()) As Integer

		If x.Length < 2 Then
			Throw New ArgumentException("More than 2 number required.")
		End If

		' test and adjust for negatives/zero values
		x = x.Where(Function(n) n <> 0).Select(Function(n) If(n < 0, -n, n)).ToArray()

		Dim v As Integer = gcd(x(x.Length - 1), x(x.Length - 2))
		For i As Integer = x.Length - 3 To 0 Step -1
			v = gcd(v, x(i))
		Next

		Return v

	End Function

	Private Function gcd(u As Integer, v As Integer) As Integer
		Return gcd(CUInt(u), CUInt(v))
	End Function

	Private Function gcd(u As UInteger, v As UInteger) As UInteger

		Dim shift As Integer
		If u = 0 Then Return v
		If v = 0 Then Return u

		shift = ctzb(u Or v)
		u >>= ctzb(u)

		Do
			v >>= ctzb(v)
			If u > v Then Swap(v, u)
			v = v - u
		Loop While v <> 0

		Return u << shift

	End Function

	' Count trailing zero bits
	Private Function ctzb(x As UInteger) As Integer

		Dim n As Integer = 1
		If (x And &Hffff) = 0 Then
			n += 16
			x >>= 16
		End If
		If (x And &Hff) = 0 Then
			n += 8
			x >>= 8
		End If
		If (x And &Hf) = 0 Then
			n += 4
			x >>= 4
		End If
		If (x And &H3) = 0 Then
			n += 2
			x >>= 2
		End If

		Return n - (x And 1)

	End Function

	Public Sub Swap(Of T)(ByRef lhs As T, ByRef rhs As T)

		Dim temp As T = lhs
		lhs = rhs
		rhs = temp

	End Sub

End module
  Permalink  
v6
Comments
PIEBALDconsult 9-Dec-16 15:23pm
   
Why would all numbers need to be positive? Mine works for negatives as well as zero.
And what about a single-item list?
Graeme_Grant 9-Dec-16 15:32pm
   
There was no request for negatives nor were they tested for.

BTW, did you post before critiquing others?
PIEBALDconsult 9-Dec-16 15:42pm
   
I have not yet. My code is not very interesting; very workman-like. I'll likely post it later as an anti-example.
Graeme_Grant 9-Dec-16 15:50pm
   
Ahhh, right.

Normally I am the same but it appears that clean code is not the point of these exercises...
Graeme_Grant 9-Dec-16 15:51pm
   
I could add a preprocessor to flip negative input values... As for single numbers, there is no GCD... only a GD.
Graeme_Grant 9-Dec-16 16:02pm
   
For completeness, I have updated the solution for you PIEBALDconsult to include 0 and negative values. :)
PIEBALDconsult 9-Dec-16 16:19pm
   
I thank you. Elvis thanks you. Elvis thanks you very much.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 5

EDIT: Updated my algorithm to allow a load for the task. MUCH better now (results posted at the end).

This was fun. I was already aware of the binary Euclidean algorithm since I've had to calculate GCDs before. So to add my own uniqueness to this problem I decided to work out a way to run the problem in parallel since the recursive binary Euclidean algorithm doesn't really give much room for uniqueness (every path except one is a tail-call so is optimized into a JMP).
public static class GCD
{
    public static uint CalculateParallel(List<uint> numbers, int taskLoad)
    {
        int totalTasks = numbers.Count / taskLoad;
        Task<uint>[] gcdTasks = new Task<uint>[totalTasks];
        for (int i = 0; i < totalTasks; i++)
        {
            int startIndex = i * taskLoad;
            gcdTasks[i] = Task.Run(() => 
                CalculateGCDForRange(numbers, startIndex, taskLoad));
        }

        uint gcd = 0;
        int remainingNumbers = numbers.Count % taskLoad;
        if (remainingNumbers > 0)
            gcd = CalculateGCDForRange(numbers, totalTasks * taskLoad,
                                       remainingNumbers);

        Task.WaitAll(gcdTasks);
        foreach (Task<uint> task in gcdTasks)
            gcd = BinaryEuclidGCD(gcd, task.Result);
        return gcd;
    }

    public static uint CalculateGCDForRange(List<uint> numbers, int startIndex, int count)
    {
        uint gcd = numbers[startIndex];
        for (; count > 1; count--)
            gcd = BinaryEuclidGCD(gcd, numbers[++startIndex]);
        return gcd;
    }

    public static uint BinaryEuclidGCD(uint firstNumber, uint secondNumber)
    {
        if (firstNumber == 0)
            return secondNumber;
        if (secondNumber == 0 || firstNumber == secondNumber)
            return firstNumber;

        //Cases where at least one number is even
        if ((firstNumber & 1) == 0)
        {
            if ((secondNumber & 1) == 0)
                return BinaryEuclidGCD(firstNumber >> 1, secondNumber >> 1) << 1;
            else
                return BinaryEuclidGCD(firstNumber >> 1, secondNumber);
        }
        if ((secondNumber & 1) == 0)
            return BinaryEuclidGCD(firstNumber, secondNumber >> 1);

        //Cases where both numbers are odd
        if (firstNumber > secondNumber)
            return BinaryEuclidGCD((firstNumber - secondNumber) >> 1, secondNumber);
        return BinaryEuclidGCD((secondNumber - firstNumber) >> 1, firstNumber);
    }
}


Test:
static void Main(string[] args)
{
    List<uint> numbers = GenerateList(3571, 1000000);
    Stopwatch sw = new Stopwatch();
    sw.Start();
    uint result = GCD.CalculateGCDForRange(numbers, 0, numbers.Count);
    sw.Stop();
    Console.WriteLine($"Sequential GCD: {result}");
    Console.WriteLine($"Time (ms): {sw.ElapsedMilliseconds}");
    sw.Reset();
    sw.Start();
    result = GCD.CalculateParallel(numbers, 10000);
    sw.Stop();
    Console.WriteLine($"Parallel GCD: {result}");
    Console.WriteLine($"Time (ms): {sw.ElapsedMilliseconds}");
    Console.ReadKey();
}

//Accepts a seed value up to 3571, the 500th prime.  Past that will be out
//of range for a uint unless a smaller maxRange is specified.
private static List<uint> GenerateList(int seed, int count, int maxRange = 1200000)
{
    List<uint> values = new List<uint>(count);
    Random rnd = new Random();
    for (; count > 0; count--)
        values.Add((uint)(seed * rnd.Next(maxRange)));
    return values;
}


Updated Results: Running 1,000,000 numbers with a GCD of 3571 I get the following results:
Sequential GCD: 3571
Time (ms): 523

Parallel GCD: 3571
Time (ms): 158
  Permalink  
v12
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 8

There are no much left as all the math used, but I on my way to create a 6502 (on C=64) solution, so I created a JavaScript prototype, to show that it is possible to do this without actually divide anything...

var a = [266, 8664, 1216, 3648];
var l = a.length;

while (l > 1)
{
    for (var k = 0; k < l - 1; k++)
    {
        if ((a[k] == 0) || (a[k + 1] == 0))
        {
            a[0] = NaN;
            break;
        }

        a[k] = gcd(Math.abs(a[k]), Math.abs(a[k + 1]));
    }

    if (isNaN(a[0])) break;

    l--;
}

// a[0] is the GCD

function gcd(x, y) {
    var d = 0;

    do
    {
        if (x == y) return x * Math.pow(2, d);

        if (!(x & 1) && !(y & 1))
        {
            x = x >> 1;
            y = y >> 1;

            d++;

            continue;
        }

        if (!(x & 1))
        {
            x = x >> 1;

            continue;
        }

        if (!(y & 1))
        {
            y = y >> 1;

            continue;
        }

        if (x > y) x = (x - y) >> 1;
        if (y > x) y = (y - x) >> 1;
    } while (true);
}

Live - JSFiddle[^]
  Permalink  
Comments
Graeme_Grant 12-Dec-16 18:10pm
   
If you look at other solutions above, they too don't use division. Also known as Binary GCD.
Kornfeld Eliyahu Peter 13-Dec-16 2:21am
   
Except your solution all use % or even /...
However my point was toward the 6502 - there is no division or multiplication there, only add and subtract...
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 12

another c example(Not expecting to be the finest)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int get_smallest_number(int *array, int length) {
    int *arr=array;
    int small=arr[0];
    int i;
    for(i=1;i<length; i++) {
        if(small>arr[i]) {
            small=arr[i];
        }
    }
    for(i=0;i<length;i++){
        if(arr[i]==small){
            arr[i]=0;
        }
    }
    return small;
}

int get_all_divisor(int number, int *to_ret) {
    int i;
    int *to_ret_ref=to_ret;
    int count=1;
    to_ret_ref[0] = 1;
    for(i=2;i<=number/2;i++) {
        if(number%i==0) {
            to_ret_ref[count] = i;
            count++;
        }
    }
    to_ret_ref[count] = number;
    count++;
    return count;
}
int gcd(int *numbers, int length_number, int *divisors, int lengt_divi) {
    int i, j;
    for(i=0;i<length_number;i++) {
        if(numbers[i]!=0) {
            for(j=lengt_divi-1;j>=0;j--){
                if(divisors[j]!=0 && numbers[i]%divisors[j]!=0){
                    divisors[j]=0;
                }
            }
        }
    }
    for(j=lengt_divi-1;j>=0;j--) {
        if(divisors[j]!=0) {
            return divisors[j];
        }
    }
    return -1;
}
int main(int args, char **argv) {
    int i;
    int *arr=malloc((args-1) * sizeof(int));
    int smallest, divisor_count;
    int *divisors;
    for(i=1;i<args; i++){
        arr[i-1] = abs(atoi(argv[i]));
    }

    smallest=get_smallest_number(arr, args-1);
    if (smallest == 1) {
        printf("1\n");
        return 0;
     }
     divisors=malloc(((int)(smallest/2) + 1) * sizeof(int));
     divisor_count=get_all_divisor(smallest, divisors);
     printf("%d\n", gcd(arr, args-1, divisors, divisor_count));
     free(arr);
     free(divisors);
     return 0;
 }
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web06 | 2.8.181207.3 | Last Updated 16 Dec 2016
Copyright © CodeProject, 1999-2018
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100