Pattern Matching Randomness

Martin writes a program and realises that he didn't do a particularly good job.

I'd been working in industrial research for some time. My biochemistry days were long behind me and I was now a computer programmer. Quite a good scientific one, I thought. At least I was reasonably competent FORTRAN coder.

ERNIE, the Random Number Generator for British Premium Bonds

Now the next laboratory along from the Computer Science department housed the electron microscopy department. Known as the "Jim'll Fix It" for its obscure role in a TV programme from that era, it was home to significant amounts of computing power on its own right. They had a dedicated 16-bit machine with 8-inch floppy disk drives. For one of their experiments they needed a stream of random numbers. This being that happy time when software libraries were less well endowed than they are now, one simply coded something up oneself. So it fell to me to write the necessary pseudo-random number generating subroutine. Hubris not withstanding, I realised the my knowledge of Number Theory would not allow me to write one from scratch. Better then to hit the library and do some reading on the Linear Incongruential method that these things seemed to use. I eventually found a very cribable example in a standard programming textbook. I translated this from the original, then new and fashionable, Pascal into 16-bit FORTRAN and presented to the microscopists. I thought that I'd done a good job. It certainly seemed to produce a stream of numbers that didn't appear to have any pattern to them when printed out.

Later, one the microscopists, suspecting that the processed results from one of his experiments was not entirely correct, had plotted the supposedly random outputs from my subroutine across the screen of his computer as a series of dots. The shading of the dots were driven by my code and therefore supposed to be random. Instead of a uniformity of grey that he should have gotten, he saw a pretty wavy pattern. I was shown the results, but my offer to try and fix this was not taken up.

I later learnt, much later, that I'd repeated a classical textbook error. The original material was wrong too. It seems that random number generators are generally hard to do. And I was in some good company. One of the original authors of UNIX had coded one that returned odd, then even, then odd numbers consecutively ad-infinitum.

It proved a valuable lesson, if a slightly painful one to my pride anyway. At this stage of the career, I'd decided that, although I was a graduate in the biological sciences, I'd found my inner computer programmer and that I was quite good at it. Hubris often is the mother of a prat-fall, and in this instance it certainly was. I wonder what my face looked like when I was shown the wavy lines. Prompted by this I've studied the whole area of random number generation a little more thoroughly. It is both interesting and mathematically intense. You've got to know what you're doing and even experts with several years in the field can make something of a bog of it. So what would I do now, faced with a similar request. I think I'd defer to the operating system. Modern UNIX influenced operating systems generally have well studied and mathematically correct random number generators (see random(3) in your favourite).

But that Random Number generators are hard to write wasn't the only thing that was learnt in this particular episode. The un-randomness of the code in question wasn't spotted by machine. It was spotted by a human, and an Electron Microscopist to boot. Humans are very good at spotting patterns in random data. They just need the data presented to them in an appropriate way. Lists of numbers was bad, but a graphical representation on a screen revealed it quite quickly.

Grogono's Random Number Generator: Grogono P (1984) Programming in Pascal, 2nd Ed., Addison-Wesley, 1984, pp. 135-137

Critique: Park SK, Miller KW (1988) "Random number generators: good ones are hard to find", Communications of the Assoc. Comp. Mach. 31(10) pp. 1192-1201 (DOI: http://doi.acm.org/10.1145/63039.63042)

Langå, 18th August 2010.

~Z~

Navigation

This is some navigation, it should appear at the side if the page is wide, and at the bottom if it is not.

Gormless Anecdotes

Martin is known for his long-winded e-mails and has decided to inflict them on the Internet like this, suitably cleaned up and formatted. There's the starting page with some explanation, and then, so far:

• Hunting the Flush Bug
• Chemi-Luminescent Vim
• Helping With an Enquiry
• Light From Under the Door
• I Write Like David Foster Wallace
• The Origami Artist
• Pattern Matching Randomness
• The Indole Chemistry of Bananas
• Volunteer Projectionist

Also of Interest

Jucy morsels from the rest of the site:

• General papers on On-line Transaction Processing (OLTP). It's still the main topic of the web-site.
• Some site news; it's a sort of infrequently updated journal for Martin too.
• Rather specific Technical Notes, Martin can still bore people in the Third-person past tense.
• Of the little hacks that he's done recently, the Unofficial Jobcentre Plus Mirror is the one thing that seems to have gained traction.
• Other ephemeral, eclectic stuff. Mostly photographs.