StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy is my implementation of the parking lot test for random number generators producing bad results?
text
Body
copied!<p>I'm trying to write an implementation of the parking lot test for random number generators. Here are the sources that I'm getting my information about the test from: <a href="http://software.intel.com/sites/products/documentation/doclib/mkl_sa/11/vslnotes/8_3_10_Parking_Lot_Test.htm" rel="nofollow noreferrer">Intel math library documentation</a> and <a href="http://www.sci.brooklyn.cuny.edu/~whitlock/parking.pdf" rel="nofollow noreferrer">Page 4 of this paper</a> along with the phi function for probability density listed <a href="http://en.wikipedia.org/wiki/Phi" rel="nofollow noreferrer">here</a>.</p> <p>I wrote an implementation of the test in C#. It uses a 100x100 grid whose values are initially set to null. I then use the random number generator to generate random integers for x and y. If that index of the grid and it's neighbors are empty, that index gets set to 1. Otherwise, nothing happens because there was a "crash". </p> <p>I ran it using C# System.Random generator. I don't believe the results are correct because I always get very near 3079 points parked, which is about 500 short of the average I'm supposed to get. It's also yields a p-value of 2.21829146215425E-90. </p> <p>My code is below. Does anyone have any experience with this or can anyone see something that I might be doing incorrectly in my implementation? Any help would be greatly appreciated. </p> <pre><code> private void RunParkingLotTest() { points = new int?[100,100]; int parked = 0; for (int i = 0; i < 12000; i++) { int x = random.Next(100); int y = random.Next(100); if (IsSafeToPark(x, y)) { points[x, y] = 1; parked++; } } Console.WriteLine("Parked: " + parked + "\nP value: " + PhiFunction((parked-3523)/21.9)); } private bool IsSafeToPark(int x, int y) { return PointIsEmpty(x, y) && LeftOfPointIsEmpty(x, y) && RightOfPointIsEmpty(x, y) && BelowPointIsEmpty(x, y) && AbovePointIsEmpty(x, y); } private bool AbovePointIsEmpty(int x, int y) { if (y == 99) { return true; } else return points[x, y + 1] == null; } private bool BelowPointIsEmpty(int x, int y) { if (y == 0) { return true; } else return points[x, y - 1] == null; } private bool RightOfPointIsEmpty(int x, int y) { if (x == 99) { return true; } else return points[x + 1, y] == null; } private bool LeftOfPointIsEmpty(int x, int y) { if (x == 0) { return true; } else return points[x - 1, y] == null; } private bool PointIsEmpty(int x, int y) { return points[x, y] == null; } private double PhiFunction(double x) { //ϕ(x) = (2π)−½e−x2/2 return ((1 / Math.Sqrt(2 * Math.PI)) * Math.Exp(-(Math.Pow(x, 2)) / 2)); } </code></pre> <p>edit - The problems with my original implementation were</p> <ul> <li>I was plotting squares instead of disks</li> <li>I only plotted points at integer values. I should have used decimal values instead.</li> <li>As a result of the above two, I needed to change my distance check</li> </ul> <p>Thanks to Chris Sinclair and mine z for help in figuring this out. The final code is posted below. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload