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')

• Grajdeanu Alex: Welcome to codereview! I don't understand, does your code run as expected or not ?
• 200_success: The code appears to work for small numbers, so I've put the time-limit-exceeded tag on it.

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.

• oba2311: Thank you @200_success♦ .All your comments but the one with the looping shortcut are welcomed. As per looping - you hardcode part of the problem for the sake of simplicity, but I was asked to design a solution for a more general problem. (circle doesn't necessarily inscribed in the square). Anyways - very helpful and help appreciated.
• oba2311: One more thing - as per errobar, I created it as some dummy so I can submit the question; now I use confidence intervals. I'm happy for suggestions tho.