Calculate PI in Java. Wrong value

Question

I'm trying to calculate PI using the Gregory-Leibniz algorithm but I'm always getting wrong values only using multi-threading. Single thread works fine.

I think the issue is the k value that is shared and the calculation messes up.

Wrong PI Value:

Select an option: 4 How many points? 100000 How many threads? 32 Concurrent Gregory-Leibniz estimated PI value : 2.7663972054374577. Executed in 121.578657 ms.

Any help please?

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * The Class GregoryLeibniz.
 */
public class GregoryLeibniz {

    /** The in circle. */
    private double factor;

    /** The sum. */
    private double sum;

    /** The points. */
    private long points;

    /** The n processors. */
    private int nProcessors;

    private long k;


    /**
     * Instantiates a new gregory leibniz.
     *
     * @param points the points
     * @param nProcessors the n processors
     */
    public GregoryLeibniz(long points, int nProcessors) {
        super();
        this.points = points;
        this.nProcessors = nProcessors;
    }


    /**
     * The Class GregoryLeibnizImpl.
     */
    public class GregoryLeibnizImpl implements Runnable {   

        /* (non-Javadoc)
         * @see java.lang.Runnable#run()
         */
        @Override
        public void run() {
            if(k % 2 == 0) factor = 1.0;
            else factor = -1.0;

            sum += factor / (2*k +1);
        }
    }

    /**
     * Calculate PI.
     *
     * @return the double
     */
    public double calculatePI() {
        ExecutorService executor = Executors.newWorkStealingPool(nProcessors);

        for (k = 0; k < points; k++) {
            Runnable worker = new GregoryLeibnizImpl();
            executor.execute(worker);
        }

        executor.shutdown();

        while(!executor.isTerminated()) { }

        return 4.0 * sum;
    }
}

Answer 1

Each instance of GregoryLeibnizImpl needs to be operating independently. Or you need a mutex. Or both.

1. GregoryLeibnizImpl needs to take "k" as a constructor parameter and store it as member variable.

2. You need a mutex/guard around sum. Otherwise, you need to "sum up" all the results of the worker thread objects at the end of the calculatePI function.

This line:

while(!executor.isTerminated()) { }

Will burn an entire core and kill the performance of your code. Use the awaitTermination method instead.

Update

I wanted some practice, so I restructured your code for a worthy solution. Perhaps I helps....

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * The Class GregoryLeibniz.
 */
public  class GregoryLeibniz {

    /** The n processors. */
    private int nProcessors;
    private long points;
    private long itemsPerThread;
    private long itemsInFirstThread;

    /**
     * Instantiates a new gregory leibniz.
     *
     * @param points the points
     * @param nProcessors the n processors
     */
    public GregoryLeibniz(long points, int nProcessors) {
        this.points = points;
        this.nProcessors = nProcessors;
        this.itemsPerThread = this.points / this.nProcessors;
        this.itemsInFirstThread += this.itemsPerThread + this.points - this.itemsPerThread * this.nProcessors;
    }


    /**
     * The Class GregoryLeibnizImpl.
     */
    public class GregoryLeibnizImpl implements Runnable {

        /* (non-Javadoc)
         * @see java.lang.Runnable#run()
         */

        long start;
        long end;
        public double result;

        public GregoryLeibnizImpl(long start, long end)
        {
            this.start = start;
            this.end = end;
        }

        @Override
        public void run() {
            int factor = ((start % 2)!=0) ? -1 : 1;
            for (long i = start; i <= end; i++) {

                result += factor / (double)(i*2+1);
                factor *= -1;
            }
        }
    }

    /**
     * Calculate PI.
     *
     * @return the double
     */
    public double calculatePI() {
        ExecutorService executor = Executors.newWorkStealingPool(nProcessors);

        long start = 1;
        long end = itemsInFirstThread;

        GregoryLeibnizImpl [] workers = new GregoryLeibnizImpl[this.nProcessors];

        for (int t = 0; t < this.nProcessors; t++) {
            GregoryLeibnizImpl worker = new GregoryLeibnizImpl(start, end);
            workers[t] = worker;
            executor.execute(worker);
            start += this.itemsPerThread;
            end += this.itemsPerThread;
        }

        executor.shutdown();

        while (executor.isTerminated() == false) {
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
            }
        }

        double result = 0;
        for (int t = 0; t < this.nProcessors; t++) {
            result += workers[t].result;
        }

        result += 1;
        result *= 4;

        return result;

    }

    public static void main(String [] args) {

        var gl = new GregoryLeibniz(1000000, 4);
        double d = gl.calculatePI();
        System.out.println(d);
    }

}

Answer 2

You need to give your worker a copy of k. Apart from that you aren't really winning a lot by letting your workers do only one step in the sum. You should create not more workers than you have CPU (cores) available and give each a portion of the sum to calculate.

Please also note that this still leaves you with a wrong sum, because if two workers read and write to it simultaneously, one of their results will be lost.

Have each worker maintain a private sum instead, then when they are all done, add their private sums together in the main thread.

Something like this:

public class GregoryLeibnizImpl implements Runnable {
    private int start;
    private int end;
    private int sum;

    public GregoryLeibnizImpl(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {
        // loop from start to end using your sum algorithm
    }
}

Then change your loop to something like this:

    for (int k = 0; k < points; k += points / numthreads) {
        Runnable worker = new GregoryLeibnizImpl(k, k + points / numthreads);
        executor.execute(worker);
    }

You need to keep those worker instances somewhere, a list for example, so you can collect their results once done.

Answer 3

Try synchronise the run method. If you let k without mutex one thread will check modulus of k, set factor and then it will go asleep, and next thread will check modulus set (same) factor, do sum += stuff and go asleep. After that first thread will also do sum += stuff with old factor.