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


We all know the area of a circle is computed as tex_b2e2e87c34b3e5a36415bf495502200f C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages . Suppose the radius is ONE for simplicity to compute the value of tex_af13d5f3905a7f5cfa284795beaccdb6 C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages , we can have the following relations:

tex_193f967b254ad62f0e5b9df5231b6977 C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages where the is the area of the one-fourth circle and the is the area of the square.

circle C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages

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 tex_af13d5f3905a7f5cfa284795beaccdb6 C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages . This approach is known as Monto-carlo simulation method, which is generally used in many applications.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}
#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;
}

pi C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages

Obviously noticed, we can see if we have a longer computation, we have a better approximation of the tex_af13d5f3905a7f5cfa284795beaccdb6 C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm algorithms beginner c / c++ code code library math probability programming languages . 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) —

GD Star Rating
loading...
695 words
Last Post: C++ Coding Exercise - Factor Utility on Windows
Next Post: How does the 8-bit BASIC perform on Famicom Clone - Subor SB2000 - FBasic - Compute PI approximation using Monte-Carlo method

The Permanent URL is: C/C++ Coding Exercise – Finding Approximation of Pi using Monto-Carlo Algorithm

Leave a Reply