B Estimating ##\pi## with darts

[jack action]

A nice experiment to not only find a method to estimate $\pi$ but also to demonstrate how difficult pure randomness can be difficult to achieve:

​

 

[Mark44]

I've simulated this experiment in computer code. The basic idea is to generate a pair of random numbers (call them x an y) in the interval [0, 1] and then determine whether $x^2 + y^2 \le 1$. If so, the point (x, y) lies inside a quarter circle of radius 1. Such a circle has an area of $\frac \pi 4$. If many such points are generated the relative fraction of these points inside the circle should be about $\frac \pi 4$. Multiply that by 4 to get an approximation for $\pi$. Of course, you have to work with a very large number of points to get anywhere close to a reasonable value for $\pi$.

 

[jedishrfu]

Would you happen to know how good the random number generator is?

Years ago, a friend/mentor at work explained the difficulties of creating pseudo-random number generators in code. In one case, when sequential triplets of random numbers are plotted, they all lie on a plane in three-space.

 

[jedishrfu]

I like the Buffon's needle experiment:

https://en.wikipedia.org/wiki/Buffon's_needle_problem

 

[PeroK]

My preferred method is to hit the buttons on my calculator at random and eventually hit the $\pi$ button.

 

[dextercioby]

My preferred method is to hit the buttons on my calculator at random and eventually hit the $\pi$ button.

You can do that on a regular PC/laptop keyboard as well, you just have to set the keyboard language to Greek.

 

[Mark44]

Would you happen to know how good the random number generator is?

I used the RNG implemented in Microsoft's Visual Studio. Here's what the docs say about that API:

Pseudo-random numbers are chosen with equal probability from a finite set of numbers. The chosen numbers are not completely random because a mathematical algorithm is used to select them, but they are sufficiently random for practical purposes. The implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, third edition, 1997.

Years ago, a friend/mentor at work explained the difficulties of creating pseudo-random number generators in code. In one case, when sequential triplets of random numbers are plotted, they all lie on a plane in three-space.

I hadn't heard this but would be surprised to find that it's still true.

 

[jedishrfu]

IBM was impacted by it with their RANDU function

https://en.wikipedia.org/wiki/RANDU

It was because RANDU used a linear consequential generator (LCG) scheme which in general was prone to this error.

https://pmc.ncbi.nlm.nih.gov/articles/PMC285899/?page=1#supplementary-material1

Nowadays, we hope math library developers are smarter.

 

[bdrobin519]

Purely just a curiosity of mine when I saw this post. But how would an experiment such as calculating points falling around a target randomly to calculate Pi correspond or (obviously) differentiate between the Double Slit Experiment? Both experiments require a single projectile aimed at a target. I've already understood the theorem of wave properties when dealing with sub atomic particles. However my question is does this experiment possibly relate and apply to more than just darts?

 

[Mark44]

But how would an experiment such as calculating points falling around a target randomly to calculate Pi correspond or (obviously) differentiate between the Double Slit Experiment?
Both experiments require a single projectile aimed at a target.

I don't see that there is any parallel between the technique described in this thread and the Double Slit Experiment, other than the randomness of something being fired at a target.

 

[robphy]

To try out the new PF feature...

• on line 2, click $Z_{next}$ to advance N by 10
• to have it run automatically, click the ticker to the left of "Run $Z_{next}$ on the top line
• Desmos has a limit of 10000 entries for a list... unless one hacks it (https://gist.github.com/jared-hughes godmode on pg2... i haven't tried it)
• it's not perfect--more of a proof of concept.
  One would probably want to control the seed (in darts)

(updated)
www.desmos.com/calculator/pzwjfyyddl

 

[vela]

Years ago, a friend/mentor at work explained the difficulties of creating pseudo-random number generators in code. In one case, when sequential triplets of random numbers are plotted, they all lie on a plane in three-space.

I seem to recall reading this was a weakness of the random number generator built into APL.

 

[jack action]

To try out the new PF feature...

• on line 2, click $Z_{next}$ to advance N by 10
• to have it run automatically, click the ticker to the left of "Run $Z_{next}$ on the top line
• Desmos has a limit of 10000 entries for a list... unless one hacks it (https://gist.github.com/jared-hughes godmode on pg2... i haven't tried it)
• it's not perfect--more of a proof of concept.
  One would probably want to control the seed (in darts)

(updated)
www.desmos.com/calculator/pzwjfyyddl

So I tried this on PF and then again on demos; I got the same results! Is it really random? And if the results are somehow stored, why does it take so long to show the final results?

 

[robphy]

So I tried this on PF and then again on demos; I got the same results! Is it really random? And if the results are somehow stored, why does it take so long to show the final results?

In the darts folder, the second argument of the random functions sets the seed. As written, the seeds are always in the same sequence.
So, you need to have the seed set differently each time. You could have it based on a slider that you freely tune… or some other source.

 

[Mark44]

@robphy and @jack action, you need a lot more than 10,000 "darts" to get anywhere close to a reasonable approximation to $\pi$.
I wrote a program in C and assembly to do the calculations a couple of years ago. The program generated 64,000,000 pairs of double-precision (64 bits) coordinates. Even with this many points my approximation was only 3.14165.

My assembly code used AVX-512 extensions to iterate through the pairs of points, processing 8 points (16 doubles) in each loop iteration. In the loop I have a single instruction to square 8 x-values, another to square 8 y-values, another to add them together, and a final instruction to determine whether the sum was less than 1.0. With this many points calculating the result takes about 10 seconds or so.

It's possible I could get a speedup by unrolling the loop to process 16 points or 32 points or more per loop iteration so as to keep the instruction pipeline full longer, but I haven't tried this

 

[vela]

I did it in Mathematica like this:

n = 100000000;
4. BinCounts[Norm /@ RandomReal[1, {n, 2}], {0, 2, 1}][[1]]/n

It takes about 3 seconds to do 100,000,000 points on my computer.