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 |
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 |
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 |
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 |
In reply to this post by jerzy.karczmarczuk
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?
Benjamin L. Russell --- On Mon, 4/28/08, [hidden email] <[hidden email]> wrote: > From: [hidden email] <[hidden email]> > Subject: Re: [Haskell-cafe] approximating pi > To: [hidden email] > Date: Monday, April 28, 2008, 9:54 AM > 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 Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 |
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 |
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 |
On Tue, 29 Apr 2008 22:12:28 -0700 (PDT), you wrote:
>I was thinking of how to represent this process graphically on a >computer screen. The way to do this is to keep in mind that the display is only a _representation_ of the algorithm in action, it is not involved in the actual algorithm. The screen resolution is immaterial to the operation of the algorithm, which is just dealing with numbers. For every iteration of the algorithm, there should be a notification sent to the code that controls the display, and that code needs to know how to update the screen accordingly. For example, it could be that the algorithm point (0.31416,0.27183) maps to pixel (45,127) on the screen. The update code might examine that pixel and increment its intensity, or change its color, or any of a number of other things that would indicate that the pixel had been "hit." Note that multiple algorithm points will necessarily map to the same screen pixel. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Thank you; that is exactly the information that I was looking for.
Benjamin L. Russell --- On Thu, 5/1/08, Steve Schafer <[hidden email]> wrote: > From: Steve Schafer <[hidden email]> > Subject: Re: [Haskell-cafe] approximating pi > To: [hidden email] > Date: Thursday, May 1, 2008, 12:31 AM > On Tue, 29 Apr 2008 22:12:28 -0700 (PDT), you wrote: > > >I was thinking of how to represent this process > graphically on a > >computer screen. > > The way to do this is to keep in mind that the display is > only a > _representation_ of the algorithm in action, it is not > involved in the > actual algorithm. The screen resolution is immaterial to > the operation > of the algorithm, which is just dealing with numbers. For > every > iteration of the algorithm, there should be a notification > sent to the > code that controls the display, and that code needs to know > how to > update the screen accordingly. > > For example, it could be that the algorithm point > (0.31416,0.27183) maps > to pixel (45,127) on the screen. The update code might > examine that > pixel and increment its intensity, or change its color, or > any of a > number of other things that would indicate that the pixel > had been > "hit." Note that multiple algorithm points will > necessarily map to the > same screen pixel. > > Steve Schafer > Fenestra Technologies Corp. > http://www.fenestra.com/ > _______________________________________________ > 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 |
Free forum by Nabble | Edit this page |