How to approximate Pi using C++11 random number generators

The other day I learnt a method to approximate Pi if you have a random number generator for the range [0,1]. Consider a unit circle centred on (0,0) in 2D coordinates. Then one quarter of the area of the circle lies in the quadrant formed by x and y in range [0,1]. The area of the quarter circle is Pi * R^2/4, and here, R = 1 (it’s a unit circle). So we can generate a bunch of random 2D points, calculate the ratio between those that fall inside the circle and those in the outer unit square, then multiply by 4 to approximate Pi.
approximatepi
That sounds like a neat test case for the C++11 random number generators, so I thought I’d try it out. It turns out to work pretty well, if you’re prepared to use a sufficiently large number of random values.

    double approxPi( size_t points )
    {
        std::random_device rand_device;
        
        // mersenne_twister_engine is a random number engine 
        // based on Mersenne Twister algorithm.
        std::mt19937 generator( rand_device() );
        
        // We want random values uniformly distributed in [0,1]
        std::uniform_real_distribution<> unif_zero_one(0, 1);
        
        size_t points_inside{0};
        
        for (int i = 0; i < points; ++i )
        {
            auto x = unif_zero_one( generator );
            auto y = unif_zero_one( generator );
            double d = std::sqrt( x*x + y*y );
            
            if ( d <= 1.0 )
                ++points_inside;
        }
                
        return 4.0 * (static_cast<double>(points_inside) / static_cast<double>(points));
    }
}

void testApproximatePi()
{
    SHOULD_BE_APPROX( 3.14159, 0.3, approxPi( 100 ) );
    SHOULD_BE_APPROX( 3.14159, 0.1, approxPi( 1000 ) );
    SHOULD_BE_APPROX( 3.14159, 0.01, approxPi( 100000 ) );
    SHOULD_BE_APPROX( 3.14159, 0.001, approxPi( 10000000 ) );
    
    std::cout << "\n";
}

A typical run gives reasonable approximations once you get over 100,000 points:
screen-shot-2016-09-16-at-13-30-26

Leave a comment

Filed under C++, C++ Code, Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s