[Haskell-cafe] approximating pi

[David Roundy]

On Mon, Apr 28, 2008 at 09:47:44AM +0200, jerzy.karczmarczuk at info.unicaen.fr wrote:
> Benjamin L. Russell: 
> 
> >Assuming the square had 100 pixels per side, on the average, approximately 
> >how many random pixels should be plotted in the square before obtaining a 
> >reasonably good estimate of pi?
> 
> Nothing to do with Haskell... 
> 
> What do you mean by "reasonable"? This Monte-Carlo procedure is very
> inefficient anyway. The relative error falls as 1/sqrt(N) where N is the
> number of samples, so, several hundred thousands of samples may give you
> just three significant digits.
> And, at any rate, this has nothing to do with pixels, what, introduce
> one more source of errors through the truncation of real randoms? 

Indeed, Monte-Carlo is generally very inefficient, but it does have the
advantage of often allowing one to write very simple code that is thus
easily shown to be correct, and (as long as the random number generator is
good!!!) to get rigorously-correct error bars, which is something that more
efficient methods often struggle on.  For simple tasks like computing pi or
integrating smooth functions, this doesn't matter much, but it's quite a
big deal when considering methods such as Quantum Monte Carlo (although,
alas the fermion problem means that for most QMC calculations one *doesn't*
get a rigorous error bar on the calculation... it's just better than almost
any other method, and for bosons you *can* get a rigorous error bar).
-- 
David Roundy
Department of Physics
Oregon State University