13,454,554 members (55,019 online)
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 2:09am
Updated 15-Dec-16 19:06pm
v3
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.

## Solution 6

Caching prime factors

* 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))
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)
}

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

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

// Set up output prime factor collection
var outputFactors = new PrimeFactorCollection();
foreach (var i in indices)

// 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...
v2
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?

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


## 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;
}

## 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.
v2
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.

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

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 v3 ## 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]; } 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 ## 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... 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? ppolymorphe 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. ppolymorphe 9-Dec-16 14:21pm Dear Peter, there are much more efficient algorithms. ## 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. v2 ## 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 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. ## 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}");
}

//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--)
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
v12

## 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[^]
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...

## 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;
}

Top Experts
Last 24hrsThis month
 CPallini 315 Maciej Los 303 John Simmons / outlaw programmer 289 OriginalGriff 235 Jochen Arndt 170
 OriginalGriff 5,495 Maciej Los 3,075 Richard Deeming 2,065 CPallini 2,062 Jochen Arndt 1,795