Estimating Pi with random darts on dartboard - high complexity issues

Question

I've been trying to write nice snippet of code to simulate pi estimation by randomly throwing darts on a dartboard. While running the following code on high but reasonable numbers my mac doesn't plot.

When looking at it I don't find the source of such a high complexity.

I checked similar questions like this but haven't been able to find straightforward answer.

My guess is that the line plotting real pi is computationally intense - but that's just a hunch.

I'd also appreciate any comment regarding style / efficiency.

import numpy as np
import random
import math
from matplotlib import pyplot as plt



def estimatePi(r,w,h,N):
    center = (w/2.0,h/2.0)
    in_circle = 0
    for i in range(N):
        x = random.uniform(0.0,w)
        y = random.uniform(0.0,h)
        distance = math.sqrt((x-center[0])**2+(y-center[1])**2)
        if distance <= r:
            in_circle += 1
    outOfCircle=N-in_circle
    ratio = float(in_circle)/N
    #ratio = ((r**2)*pi)/(w*h)  // *(w*h)
    #ratio*(w*h) = ((r**2)*pi) // : r**2
    pi = ratio*(w*h)/(r**2)
    return pi

#run, aggregate results:
PiEstimation=[]
num_darts=[]
loopcount = 1000001
i=10000

while i <loopcount:
    result=estimatePi(3,10,10,i)
    num_darts.append(i)
    PiEstimation.append(result)
    i += 15000

# plot:
plt.title('Estimating the Value of Pi - Dartboard Simulation')
plt.plot([0,100000000], [3.14,3.14], 'k-',color="red", linewidth=2.0)
plt.ylabel('Pi Estimation')
plt.xlabel('Number of Darts')
plt.errorbar(num_darts,PiEstimation, yerr=.0001,ecolor='magenta')
plt.show('hold')

Answer 1

Performance

The biggest simple performance improvement would be to use xrange() instead of range() for the loop counter in estimatePi(). Note that i is unused; it is customary to use _ as the name of a "throwaway" variable.

I don't see much point in the r, w, and h parameters. If you make the dartboard a unit circle centered at the origin, then you could do away with the math.sqrt().

outOfCircle is never used. Its naming is also inconsistent with in_circle.

Plot quality

For a program that aims to visualize the accuracy of the technique to estimate π, you're being awfully sloppy by plotting a horizontal line at y = 3.14 rather than at math.pi. The easier way to plot a horizontal line is to use axhline().

It makes no sense to use an errorbar plot here, with an arbitrarily chosen yerr=.0001, since you have just one sample at each x.

Looping

Neither loop is as expressive as it could be.

In estimatePi(), you can calculate in_circle using sum() with a generator expression. (When coerced into an integer, True is treated as 1, and False as 0.)

To make the lists num_darts and PiEstimation, you can use range() and a list comprehension, respectively.

Suggested solution

Take care to follow PEP 8 naming conventions.

from math import pi
from random import uniform
import matplotlib.pyplot as plt

def estimate_pi(n):
    in_circle = sum(
        uniform(-1, 1)**2 + uniform(-1, 1)**2 <= 1
        for _ in xrange(n)
    )
    return 4.0 * in_circle / n

darts = range(10000, 1000001, 15000)
pi_estimations = [estimate_pi(n) for n in darts]

plt.title('Estimating the Value of Pi - Dartboard Simulation')
plt.ylabel('Pi Estimation')
plt.xlabel('Number of Darts')
plt.axhline(y=pi, color="red", linewidth=2.0)
plt.plot(darts, pi_estimations, marker='o')
plt.show('hold')

This runs in under a minute on my machine.