Beastly Coprimes

Example of how to use Web Workers on the browser and take advantage of parallel computing. For the sake of demonstration, a simple algorithm to compute coprime numbers is presented. Specifically, we need to find all coprime numbers from 1 to 1x10^6 such that added together sum the number of the beast (666).

To compute the coprime numbers, I use an algorithm called Euclid’s algorithm. For each number $1 \leq i \leq 1x10^8$, the evaluation of $GCD(i, 666) == 1$ is done and if it holds, such number $i$ is added to the final result.

# Run	Sequential Time ($T_1$)	Parallel Time ($T_8$)
1	6.80	1.26
2	6.88	1.23
3	6.74	1.22
4	6.81	1.25
5	6.83	1.25
Mean	6.81	1.24

$$S_8 = \frac{T_1}{T_8} = \frac{6.81}{ 1.24 } = 5.49$$

$T_x$ means the runtime by executing the code using $x$ threads.

As you can see, there is a great improvement on the execution time. The parallel version works almost 5.5x times faster than the sequential version.

Github Code