Optimize estimating Pi function C++

Question

I've wrote a program, that approximates Pi using the Monte-Carlo method. It is working fine, but I wonder if I can make it work better and faster, because when inserting something like ~n = 100000000 and bigger from that point, it takes some time to do the calculations and print the result.

I've imagined how I could try to approximate it better by doing a median for n results, but considering how slow my algorithm is for big numbers, I decided not doing so.

Basically, the question is: How can I make this function work faster?

Here is the code that I've got so far:

double estimate_pi(double n)
{
    int i;
    double x,y, distance;
    srand( (unsigned)time(0));
    double num_point_circle = 0;
    double num_point_total = 0;
    double final;

    for (i=0; i<n; i++)
    {
        x = (double)rand()/RAND_MAX;
        y = (double)rand()/RAND_MAX;
        distance = sqrt(x*x + y*y);
        if (distance <= 1)
        {
            num_point_circle+=1;
        }
        num_point_total+=1;
    }
    final = ((4 * num_point_circle) / num_point_total);
    return final;
}

Answer 1

An obvious (small) speedup is to get rid of the square root operation. sqrt(x*x + y*y) is exactly smaller than 1, when x*x + y*y is also smaller than 1. So you can just write:

double distance2 = x*x + y*y;
if (distance2 <= 1) {
    ...
}

That might gain something, as computing the square root is an expensive operation, and takes much more time (~4-20 times slower than one addition, depending on CPU, architecture, optimization level, ...).

You should also use integer values for variables where you count, like num_point_circle, n and num_point_total. Use int, long or long long for them.

---

The Monte Carlo algorithm is also embarrassingly parallel. So an idea to speed it up would be to run the algorithm with multiple threads, each one processes a fraction of n, and then at the end sum up the number of points that are inside the circle.

---

Additionally you could try to improve the speed with SIMD instructions.

---

And as last, there are much more efficient ways of computing Pi. With the Monte Carlo method you can do millions of iterations, and only receive an accuracy of a couple of digits. With better algorithms its possible to compute thousands, millions or billions of digits.

E.g. you could read up on the on the website https://www.i4cy.com/pi/