Randomized Pi calculation
I don't know which is the most common way to calculate Pi in computer programs, but from the stochastics book a read for my recent stochastics exam, I have a randomized variation, which is quite cool I think. To show it, I implemented it in PHP:
define( "ITERATIONS", 100 );
$precision = pow( 10, (int) ini_get( "precision" ) - 5 );
$hits = 0;
for ( $i = 0; $i < ITERATIONS; $i++ )
{
$x = mt_rand( 0, 2 * $precision ) / $precision - 1;
$y = mt_rand( 0, 2 * $precision ) / $precision - 1;
if ( ( $x * $x ) + ( $y * $y ) < 1 )
{
$hits++;
}
}
echo "Pi is about " . ( ( 4 * $hits ) / ITERATIONS );The basic assumption in this algorith is, that the generated coordinates are rectangular distributed in the rect (-1/-1) - (1,1). For the numbers I generate using mt_rand() this should be almost correct (note that the generation is not part of the algorith itself, it only says, that you need rectengular distributed points). For each of this generated points, a check is performed, if the point is located inside the unit circle. If it is, a hit is recorded. The relative frequence for this event is exactly the ratio between the unit circle and the whole square, which means it is Pi/4.
The algorith is not really fast, but gives usable results for a large number of iterations:
Iterations | Pi estimation | Time (sec.) |
100 | 3.2 | 0.000174045562744 |
1000 | 3.128 | 0.00145411491394 |
10000 | 3.1436 | 0.0180418491364 |
100000 | 3.13876 | 0.16107583046 |
1000000 | 3.143652 | 1.64533686638 |
10000000 | 3.1423896 | 18.0556662083 |
Update, 2007-04-02: Note, that you should never use this algorithm to calculate Pi in PHP! There is the predefined constant M_PI, as well as the function pi() to retrieve a value with the precision specified in your php.ini! This is just a cool algorith and it's really slow (in comparison of using the constant)!
Comments