Patterns in the PHP Random Function

When you make the finding yourself – even if you’re the last person on Earth to see the light – you’ll never forget it.
– Carl Sagan

Inspired by Oranchak’s post on Genetic Algorithms, I decided to revisit a project I left off on a few months back, the end result of which is to attempt to evolve static noise into digital images. As a preliminary step to this, I wanted to write a script where I could draw images, pixel by pixel. So I wrote a decimal to hexadecimal converter, and then incremented the RGB values in HTML to render a table in shifting colors.

Blue and Green Color Pallet (Red is set to 00)

The above image is an html table, 256 cells wide and 256 rows high, each cell with a different bgcolor and a transparent single-pixel GIF to show the color. It’s slow for the browser to display, and, in fact, IE won’t finish rendering it, but it gives me full control over every pixel’s RGB value in the image. So it’s perfect for reading images into it as an array of RGB values, and then trying to evolve another array of RGB values to match it.

The next step was to test randomizing the value of all RGB values. Easy enough, I simply plugged PHP’s rand() function into the values and refreshed the page.

Image Generated with PHP’s rand(0,255) Function

Waitaminute. It’s static-y, as expected, but what are those lines? There are numerous, distinctly unrandom-looking lines in this image. The most distinct appear to be half green on top and half purple on bottom.

I decided to copy and paste a sampling of nine of these pixel-wide 150-something pixel-high patterns into Photoshop. They don’t quite line up, but they all exhibit the same distinct pattern (rotated clockwise to conserve space).

Sample of Nine Line Patterns

Each time I render the random static, I get a new pattern, but these green-purple lines come back in different places. I took some measurements of the hexadecimal values of several lines, looking for exact matches between lines. I quickly found some, because the exact same line pattern repeats in the exact same column

Pattern A and Pattern B were both repeated in the column where they were found, and appeared to continue repeating past this sampling.

Here there’s another piece of the puzzle. I tried changing the image dimensions from 256 by 256 to 128 by 128 and 512 by 512, in both cases, the lines appeared. Changing the image dimensions to 72X72, 154X154, or any other non-binary power appears to remove the patterns completely.

So far, what I’ve been able to find on this is that the geeks at php.net have discussed the shortcomings of the rand() function, the function uses a pseudorandom number generator algorithm (probably something called libc, which is a “multiplicative congruential algorithm”), so it is expected to produce these patterns. For a much more random, but still pseudorandom, number generator, it is best to use mt_rand, which uses the Mersenne twister pseudorandom number generator, based on “matrix linear recurrence.”

I understand what I’ve read well enough to know that I presently lack even the foundational knowledge to appreciate this subject. At this point, I am content to know that human minds out there are aware of the phenomenon, and appreciate them for settling down to become experts in a subject as obscure, yet very important, as the process for generating random numbers, which are crucial to cryptography and playing Dungeons & Dragons.

You can play with a demo of what I’m talking about here. Word of warning though, it takes time for the table to render, could cause weaker systems to slow down, and I’ve had IE quit rendering it halfway down the table.

You can download the PHP file here. There’s an empty single-pixel transparent gif included that holds the table cells open to display the background color.