Testing RNGs with the Parking Lot Test

Cars are for squares

A random number generator (RNG) is a device or process that should produce unpredictable results. We rely on them in applications where randomness is critical like in simulations, research, games, and cryptography. An important concept one shouldn’t overlook is whether the output an RNG makes is actually random. For example, it’s not fair to other players if you play games with loaded dice, nor is it fun to see that the password you generated was easy for a hacker to predict.¹ Many tests for evaluating an RNG’s randomness involve analyzing the statistical properties of its outputs, but my favorite method by far is the Parking Lot Test.²

Originally invented by George Marsaglia, the Parking Lot Test evaluates how well 2D coordinate points made by an RNG are uniformly distributed by trying to find out how many randomly placed \(1 \times 1\) squares (“cars”) out of 12,000 can be sequentially placed without overlap (“parked”) in a \(100 \times 100\) square (“parking lot”).³

Let’s run the Parking Lot Test on the default RNG provided by the numpy library, the 64-bit Permuted Congruential Generator (PCG64).

import datetime
import sys

import bokeh
import numpy as np
import pylfsr
import scipy
from bokeh.io import export_png
from bokeh.plotting import figure, output_notebook, show
from scipy.stats import norm

PARKING_LOT_SIZE = 100
NUM_CARS = 12000
CAR_WIDTH = 1

# Let Bokeh show outputs as a Jupyter Notebook
output_notebook()

# Instantiate NumPy RNG & seed for reproducibility
rng = np.random.default_rng(seed=20230903)

Loading BokehJS ...

Generating Coordinates

The first step of the Parking Lot Test is to randomly generate the 12,000 \((x, y)\) coordinate pairs of the “cars” using the RNG under test. Each coordinate should be a randomly and uniformly selected sample of the range \(\left[0, 100\right]\) so that each car on its own fits inside the \(100 \times 100\) parking lot.⁴

The numpy RNG already provides a uniform function for us; let’s use it to generate each car’s \((x, y)\) coordinates and store them in a \(12,000 \times 2\) array: the first column corresponds to the x-coordinate, and the second column corresponds to the y-coordinate.

# Generate coordinate points
car_coords = rng.uniform(0, PARKING_LOT_SIZE, (NUM_CARS, 2))

Parking the Cars

Now that we have our coordinates, let’s try parking each of the cars sequentially on the parking lot. Parking the first car is easy since there are no other cars to check against. For the rest of the cars, we’ll have to check against all parked cars if there is enough space; otherwise, that car crashes.⁵

Since the cars are \(1 \times 1\) squares, we can develop a formula that determines whether a new car will “crash” (overlap) with another parked car. Let’s say that we want to place a new car at \((x_n, y_n)\) and make sure that it’s far enough from the parked car \((x_p, y_p)\). The two squares will overlap if the distance between their x-coordinates and the distance between their y-coordinates are less than or equal to 1. If this happens, we can’t park the car, so it crashes.⁶

Let’s make a 1D array of booleans to keep track of which cars are parked in the parking lot. We can use this array to select which cars we need to compare coordinates to any new car. For each new car that we want to try parking, we can check if any pair of coordinate differences are both less than 1.

def determine_parked_cars(car_coords_):
    """Run the Parking Lot test on the RNG-generated coordinates."""
    # Initialize array of booleans telling us if cars are parked
    is_parked_ = np.zeros(NUM_CARS, dtype=np.bool_)

    # Park the first car
    is_parked_[0] = True

    # For all other cars:
    for i in range(1, NUM_CARS):
        # Get the difference of coordinates from the new car & check if any
        # parked car is close enough to the new car
        car_diffs = np.abs(car_coords_[is_parked_] - car_coords_[i])
        if np.any(np.logical_and.reduce(car_diffs <= CAR_WIDTH, axis=1)):
            is_parked_[i] = False
        else:
            is_parked_[i] = True
    return is_parked_


is_parked = determine_parked_cars(car_coords)

Plotting the Results

Let’s visualize the results of the Parking Lot Test using the coordinates and the parked car index array. The probability distribution of the resulting number of parked cars follows a Gaussian distribution with a mean of 3253 and a standard deviation of 21.9; using this information, we can approximate the p-value of our result, the probability that a more extreme outcome occurs. An RNG passes the Parking Lot Test if the resulting p-value obtained by comparing the number of parked cars to the normal distribution is greater than 5%.⁷

PL_MEAN = 3523
PL_STD = 21.9


def parking_lot_figure(car_coords_, is_parked_):
    """Draw the parking lot and parked cars of the Parking Lot Test."""
    num_parked = np.count_nonzero(is_parked_)
    p_value = norm.cdf(num_parked, loc=PL_MEAN, scale=PL_STD)

    fig = figure(
        match_aspect=True,
        title=f"Parked Cars: {num_parked}, p-value: {p_value:.3f}",
        align="center",
    )
    fig.tools[2].match_aspect = True

    fig.quad(
        left=0,
        right=PARKING_LOT_SIZE,
        top=PARKING_LOT_SIZE,
        bottom=0,
        fill_color="gray",
        line_color="black",
    )

    fig.quad(
        left=car_coords_[is_parked_, 0] - CAR_WIDTH / 2,
        right=car_coords_[is_parked_, 0] + CAR_WIDTH / 2,
        top=car_coords_[is_parked_, 1] + CAR_WIDTH / 2,
        bottom=car_coords[is_parked_, 1] - CAR_WIDTH / 2,
        fill_color="green",
        line_color="black",
    )

    return fig


# Draw figure for HTML export
fig = parking_lot_figure(car_coords, is_parked)
# Draw figure for PNG export
fig2 = parking_lot_figure(car_coords, is_parked)
export_png(fig2, filename="pcg64_plt.png")

Static Image

Parking Lot Test Results for the PCG64 random number generator.

Interactive Plot

show(fig)

Parking Lot Test Results for the PCG64 random number generator.

Repeating Results with a Bad RNG

Our results from the previous section show that the PCG64 from the numpy library passed the Parking Lot Test. What would the test results from a bad RNG look like? Let’s compare the parking lot test results between the PCG64 and another RNG, the 16-stage linear feedback shift register (LFSR) from the pylfsr library. The LFSR is a digital circuit whose outputs are pseudorandom but much more correlated than the PCG64.

lfsr = pylfsr.LFSR([16, 5, 3, 2])
lfsr_seq = lfsr.getFullPeriod()

# Initialize & Generate Car Coordinates
car_coords = np.zeros((NUM_CARS, 2))
for i, (x, y) in enumerate(np.ndindex((NUM_CARS, 2))):
    rand_bits = lfsr_seq.take(range(i * 16, i * 16 + 16), mode="wrap")
    l_rand = (
        sum([(2 ** -(j + 1)) * a for j, a in enumerate(rand_bits)]) * PARKING_LOT_SIZE
    )
    car_coords[x, y] = l_rand

# Run & plot the Parking Lot Test
is_parked = determine_parked_cars(car_coords)

# Draw figure for HTML export
fig = parking_lot_figure(car_coords, is_parked)
# Draw figure for PNG export
fig2 = parking_lot_figure(car_coords, is_parked)
export_png(fig2, filename="lfsr16_plt.png")

Static Image

Parking Lot Test Results for the 16-stage LFSR.

Interactive Plot

show(fig)

Parking Lot Test Results for the 16-stage LFSR.

Conclusion

The PCG64’s Parking Lot Test results evidently look denser than the results from the 16-stage LFSR, since more cars are parked in the former than the latter. You can notice that there are some patterns present in the LFSR’s parking lot that are visible if you squint.

The original description of the Parking Lot Test describes the shape of the cars as “unit circles”, i.e., circles with radius 1. As Robert G. Brown had commented source code of DIEHARDER, diving into the actual code itself reveals that Marsaglia’s distance evaluation didn’t match with the documentation.⁸ This tripped me up, too; my first draft of the code used unit circles for the cars instead of squares, so it took me some time to realize that something didn’t match up right.

Note

While the PCG64 & 16-stage LFSR were good examples for demonstrating the Parking Lot Test, they are both pseudo-random number generators (PRNGs) - their outputs look random, but are ultimately driven by an internal ruleset and a starting value called a seed. I don’t recommend using either of these RNGs in a serious cryptographic application.

Package Versions & Last Run Date

Python 3.13.5 (main, Jun 25 2025, 18:55:22) [GCC 14.2.0]
Bokeh 3.8.0
NumPy 2.3.3
PyLFSR 1.0.7
SciPy 1.16.2
Last Run 2025-10-04 12:26:07.464014

References

Brown, Robert G. “Dieharder: A Random Number Test Suite,” March 2020. https://webhome.phy.duke.edu/~rgb/General/dieharder.php.

Intel. “Notes for Intel® oneAPI Math Kernel Library Vector Statistics.” Intel, December 2020. https://www.intel.com/content/www/us/en/docs/onemkl/developer-reference-vector-statistics-notes/2021-1/overview.html.

Stipčević, Mario, and Çetin Kaya Koç. “True Random Number Generators.” In Open Problems in Mathematics and Computational Science, edited by Çetin Kaya Koç, 275–315. Cham: Springer International Publishing, 2014. https://doi.org/10.1007/978-3-319-10683-0_12.

Footnotes

1. Stipčević and Koç, “True Random Number Generators”.

2. Intel, “Intel® oneAPI Math Kernel Library”.

3. Intel.

4. Brown, “Dieharder”.

5. Brown.

6. Brown.

7. Intel, “Intel® oneAPI Math Kernel Library”.

8. Brown, “Dieharder”.