On Mon, 2008-04-28 at 02:54 +0200, jerzy.karczmarczuk@info.unicaen.fr 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.)

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

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, jerzy.karczmarczuk@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?

Jerzy Karczmarczuk

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org 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 wrote:

From: Steve Schafer Subject: Re: [Haskell-cafe] approximating pi To: haskell-cafe@haskell.org 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe