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;
}
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;
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:
var integers = [247, 8645, 1216, 3648];
var lowerBound = 1;
var upperBound = Math.min(...integers);
var populationSize = 10;
var population = [];
var maxIteration = 20;
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>";
population = generatePopulation(population, populationSize, lowerBound, upperBound);
desc += "Candidates at start: " + population + "<br>";
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);
j--;
break;
}
}
}
desc += "Candidates left: " + population + "<br>";
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...