CODEWITHSUNDEEP
javaparallel-processing
XaNNy0
XaNNy0

Reputation: 179

The parallelization takes longer than the non-parallelized task

I need to do a programming assignment for the university. The task is to implement a program that returns all solutions of the equation q² + 3qp + p² = r² (q,p,r prime numbers). Subsequently, the program is to be speeded up by parallelization. Unfortunately we have to use BigInteger, so don't be surprised.

This is my class I wrote that calculates exactly this equation.

    public boolean calculateEquation() {
    //Equation: p² + 3pq + q² = r²
    if (calculatePSquare().add(calculate3TimesPQ()).add(calculateQSquare()).equals(calculateRSquare())) {
        System.out.println("p: " + p + " q: " + q + " r: " + r);
    }
    return calculatePSquare().add(calculate3TimesPQ()).add(calculateQSquare()).equals(calculateRSquare());
}
@Override
public void run() {
    calculateEquation();
}

Full code for that class: https://pastebin.com/wwrDurUT

My next step was to test the code and stop the time to see if the parallelization works later. To implement the parallelization I have looked at different threads, among others also the one linked here: What is the easiest way to parallelize a task in java?

And this was my result:

ExecutorService executorService = Executors.newFixedThreadPool(Configuration.instance.maximumNumberOfCores);
        ExecutorCompletionService executorCompletionService = new ExecutorCompletionService(executorService);

        for (BigInteger pValue : possiblePValues) {
            for (BigInteger qValue : possibleQValues) {
                for (BigInteger rValue : possibleRValues) {
                    executorCompletionService.submit(new Thirteen(pValue, qValue, rValue), null);
                }
            }
        }
        executorCompletionService.take();

Full code: https://pastebin.com/kviEnnFH

Now to what's funny, the parallelized version is only faster if the number of tasks is small. For all primes between 0-500, the parallelized version is faster. If I take all primes between 0 and 2000, the results look very different:

All primes between 0 and 100:

Not parallelized: Task took: 110ms

Parallelized: Task took: 64ms

All primes between 0 and 2000:

Not parallelized: Task took: 7797ms

Parallelized: Task took: 25799ms

Since there are so few easily understandable resources on the subject, and I honestly don't quite understand what exactly the code of mine does, I'm very surprised why it behaves as it does.

Upvotes: 4

Views: 225

Answers (1)

Ervin Szilagyi
Ervin Szilagyi

Reputation: 16795

First of all, there is no point in implementing this p² + 3pq + q² = r² equation using a triple embedded for loops, which results in having a complexity of O(n) = n^3. This can be done using only two for loops since if we know the value of p and q, r can be calculated using the equation.

for (BigInteger p: possiblePValues) {
    for (BigInteger q: possibleQValues) {
        BigInteger r = p.pow(2).add(q.pow(2)).add(p.multiply(q).multiply(new BigInteger("3")))
        // decide if sqrt(r) is prime
     }
 }

Now if we have saved the pre-computed primes inside of a Hashmap for example, we can determine if r is prime instantly with a lookup.

About the parallalization: Your approach is wrong, since you are just spawning threads for some operations which take relatively short amount of time to complete. Probably the overhead of thread management takes longer then the operation to calculate the equation itself. I guessing that's why you get longer running period for multithreaded version. There is no golden rule on how to parallelize two embedded for loops. My approach would be to split the first loop in smaller chunks depending on how many cores you have and create some intervals. For example, if we have 100 primes and 4 threads, the first thread will take the p values having the index from 0 to 24, the second from 25 to 49 and so on. The second for loop should run from 0 to 100 in every thread. Using this approach you can compute all the possible r values.

Upvotes: 1

Related Questions