C/C++ Coding Exercise – Finding Approximation of Pi using Monto-Carlo Algorithm

We all know the area of a circle is computed as . Suppose the radius is ONE for simplicity to compute the value of , we can have the following relations:

where the c is the area of the one-fourth circle and the n is the area of the square.

Knowing this, we just have to generate a certain number of points within the square area (both coordinates smaller or equal to one), and count the number of times that the points fall within the circle.

The following C++ program tests for a number of iterations. Each point generated, we check the square distance between the zero, if it is smaller than 1, then it is within the circle, we increment the counter. At last, we compute the ratio and multiply by four, which gives the approximation of the . This approach is known as Monto-carlo simulation method, which is generally used in many applications.

#include <iostream>
#include <time.h> // time
#include <stdlib.h> // srand

using namespace std;

int main() {
    srand(time(NULL));
    cout.precision(10);
    cout << "HelloACM.com rocks!" << endl;
    const int N[] = {1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9};
    for (int j = 0; j < (sizeof(N) / sizeof(N[0])); j ++) {
        int circle = 0;
        for (int i = 0; i < N[j]; i ++) {
            double x = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
            double y = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
            if (x * x + y * y <= 1.0) circle ++;
        }

        cout << N[j] << (char)9 << (char)9 << (double)circle / N[j] * 4.0 << endl;
    }
    return 0;
}

Obviously noticed, we can see if we have a longer computation, we have a better approximation of the . However, this method highly depends on the pusdo-random number generator, that is why we have a srand() function to set the random seed according to time function in the beginning.

It is noticed that the accuracy is still limited because we hold the value using the double type. The accuracy entirely depends on the probability, which means suppose we have run the program long enough (e.g. forever), the ratio between the points falling in the circle with the total number (falling in the square) is the one-fourth of the value pi because the radius of the circle (and the edge of the square length) is one.

–EOF (The Ultimate Computing & Technology Blog) —