Monte Carlo Pi

Using randomness to solve problems that might be deterministic in principle. It is useful in circumstances when there is a simple test to verify if some solution is valid or invalid, many guesses are (uniformly) generated in the potential domain and their validity checked, then the proportion of valid guesses approximates to the solution.

Examples

This is a single threaded approximation of the value of π. It can calculate a trillion guesses in around ten seconds, the multithreaded version on my four core ThinkPad performs the same amount of guesses in around five seconds. An impressive loss of efficiency…

Here we ride the monoid, using some properties of the “unit” or “identity” element under multiplication to relate the unit square and unit circle to find π. Which is to say we’re using the number one a lot because 1*1 = 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// We provide the number of guesses to make
func monte_carlo_pi(reps int) float64 {
    // Ready our places
    var x, y float64
    count := 0
    seed := rand.NewSource(time.Now().UnixNano())
    random := rand.New(seed)

    // Perform the experiment
    for i := 0; i < reps; i++ {
        // Choose a random point in the unit square
        x = random.Float64()
        y = random.Float64()

        // Test if point is in the unit circle
        if num := x*x + y*y; num < 1 {
            count++
        }
    }
    // The unit square is only in the first quadrant
    // The unit circle is in all four, so adjust.
    return (float64(count) / float64(reps)) * 4
}