approximating pi

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

approximating pi

ryah dahl
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

Don Stewart-2
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

jerzy.karczmarczuk
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

Derek Elkins
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

Benjamin L. Russell
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

jerzy.karczmarczuk
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

David Roundy-2
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

Benjamin L. Russell
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

Steve Schafer
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
Reply | Threaded
Open this post in threaded view
|

Re: approximating pi

Benjamin L. Russell
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