# approximating pi Classic List Threaded 10 messages Open this post in threaded view
|

## approximating pi

 By picking points randomly from a square one can calculate pi. Keep track of how many points from the square you pick lay in the inscribed circle. Supposing the square's edges are length 2, then the inscribed circle has radius 1. Thus the area of the circle is pi*r^2 = pi. The area of the square is 4.  The ratio of points picked from the circle to the total number of picked points will converge to pi / 4. What is the best way to express this algorithm in Haskell? ry _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: approximating pi

 ry: > By picking points randomly from a square one can calculate pi. Keep > track of how many points from the square you pick lay in the inscribed > circle. Supposing the square's edges are length 2, then the inscribed > circle has radius 1. Thus the area of the circle is pi*r^2 = pi. The > area of the square is 4.  The ratio of points picked from the circle > to the total number of picked points will converge to pi / 4. > > What is the best way to express this algorithm in Haskell? Using a random generator, such as System.Random or System.Random.Mersenne, generate random numbers in your range, testing if they're inside the circle, and loop until your limit condition is reached. The full program is about 10 lines or so, so shouldn't be too hard to work out, once you've worked out how to generate Doubles from System.Random.random -- Don _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: approximating pi

 Don Stewart writes: > Ry Dahl: >> By picking points randomly from a square one can calculate pi. ... >> What is the best way to express this algorithm in Haskell? > > Using a random generator, such as System.Random or > System.Random.Mersenne, generate random numbers in your range, > testing if they're inside the circle, and loop until your limit > condition is reached. > > The full program is about 10 lines or so, so shouldn't be too hard to > work out, once you've worked out how to generate Doubles from > System.Random.random Ry Dahl seems to know Ruby. Ruby has also comprehensions. So, why not use 'randoms' to generate an infinite list of them, 'take' some N, and then 'sum' 1 on randoms filtered by the circle condition. I think that you won't need full 10 lines of code... Jerzy Karczmarczuk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: approximating pi

 On Mon, 2008-04-28 at 02:54 +0200, [hidden email] wrote: > Don Stewart writes: > > > Ry Dahl: > >> By picking points randomly from a square one can calculate pi. > ... > >> What is the best way to express this algorithm in Haskell? > > > > Using a random generator, such as System.Random or > > System.Random.Mersenne, generate random numbers in your range, > > testing if they're inside the circle, and loop until your limit > > condition is reached. > > > > The full program is about 10 lines or so, so shouldn't be too hard to > > work out, once you've worked out how to generate Doubles from > > System.Random.random > > Ry Dahl seems to know Ruby. Ruby has also comprehensions. So, why not use > 'randoms' to generate an infinite list of them, 'take' some N, and then > 'sum' 1 on randoms filtered by the circle condition. I think that you > won't need full 10 lines of code... Indeed.  I just stuck in one line into lambdabot to do this.  As an actual executable and more nicely factored/laid out I'd say it would probably be about 8 wc -l lines (that is everything, the module declarations, imports, blank lines, etc.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: approximating pi

Open this post in threaded view
|

## Re: approximating pi

 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? Jerzy Karczmarczuk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: approximating pi

 On Mon, Apr 28, 2008 at 09:47:44AM +0200, [hidden email] 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: approximating pi

 In reply to this post by jerzy.karczmarczuk I was thinking of how to represent this process graphically on a computer screen.  Assuming one wanted to perform a demo of this algorithm (in the spirit of XTANGO, an algorithm animator that I had used for my senior project in 1994), in order to represent the square and the circle on-screen, one would need to represent the objects with pixels.  Many desktop and laptop computer screens these days have a minimum resolution of 800x600 pixels; assuming this resolution, I wanted to see how this algorithm could be animated using a square with 100 pixels per side. The problem is how to define "reasonable."  As you stated, since the relative error falls as 1/sqrt(N), where N is the number of samples, and 100x100=10000 pixels, then for, say, even a relative error of 1/100, we would need to fill up the entire square (10000 pixels).  I would really like a relative error of 1/1000, in which case we would need 1000x1000=1000000 samples, which would require filling up a square ten times longer per side. This is unlikely to work in practice with most desktop and laptop computer screens; so, I'll lower my expectations slightly.  I'll be very lenient and set my acceptable relative error to 1/10.  Then, since the relative error falls as 1/sqrt(N), since sqrt(100)=10, N can be 100.  The square has an area of 100x100=10000 pixels. This would allow a very rough estimate of pi that could actually be demonstrated graphically using an algorithm animator. Benjamin L. Russell --- On Mon, 4/28/08, [hidden email] <[hidden email]> 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? > > Jerzy Karczmarczuk > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe