Circular Cruises/Random
From Eccentric Flower
 |
Random 2 December 1997 In the world of random numbers, "random" really means Random Enough. Truly Random things are hard to come by. Oddly enough, to achieve real randomness you have to go to simple phenomena. Rolling a die is a really good way to get close to Truly Random with very little effort. It's true that if you always roll a die the same way, you may be achieving less randomness than you think; it's true that most dice have minute manufacturing defects which favor certain sides an infinitesimal amount - but dice, and coin-flipping, are way up there on the Random Enough scale. A die is Random Enough for most of us. - - - Unfortunately, there aren't any ten-thousand-sided dice, so people who need a very large range of randomly chosen numbers have to use other methods. "Other methods" in this case generally means a computer. Here's a poorly-kept secret: Computers are lousy at being random. But they're pretty good at being Random Enough. For most business applications - for example, choosing a number to put on a new credit card (no, they're not given out serially) - computers do a decent job. Computers make random numbers in different ways depending on the system, but it's all basically voodoo, since computers don't actually have a way to "roll a die" internally. (Or, with extra jargon: Computers do not possess a true non-deterministic method of generating numeric values.) Don't look smug - you don't either. Humans are just as lousy at picking random numbers. We tend to either unconsciously insert patterns, or too scrupulously try to avoid patterns (which is itself a pattern). We may not use a mathematical algorithm that we're aware of, but that doesn't mean anything. We have no idea what's going on in the gray matter. Many "random" phenomena - phenomena which, let it be said, are usually Random Enough - turn out to have underlying rules after all, just very complex ones. Weather is an algorythmic system, but the rulebook is so complex that it's hard for our puny analytical methods to get a handle on it. Clouds were thought to be random, until fractals came along and could be used to generate some exceedingly cloudlike shapes. Does this mean that clouds are shaped by fractal mathematics? No ... but it also means we can no longer be as sure that there isn't something deterministic underlying their shapes. - - - But back to computers. Here's the description of the random-number function on a Solaris unix computer: rand() uses a multiplicative congruential random-number generator with period 2^32 that returns successive pseudo-random numbers in the range from 0 to (2^15)-1. Don't worry, I don't understand it either. Most programming languages have a rand() function of some kind or another, and they all have the same fault: they make a random-looking list of numbers, but unless you take steps to prevent this, it'll always be the same list. In other words, if you're writing in Perl and you say To avoid this problem, there is generally a provision to give the random-number generator a "seed" at the beginning of your program - a starting value which will determine the sequence to come. The problem is that if you use the same seed every time, you still get the same sequence of numbers. (Both of these paragraphs actually say the same thing. If you don't provide a seed, as in the first paragraph, the random number generator uses its favorite seed every time - same result as the second paragraph.) Think of the seed as being shorthand for "which sequence of numbers shall I use today?" Clearly, what you really want to do is pick a different seed every time the program runs. But in order to do that, you'd need a random number. The way around this little catch is to provide a seed which is some value that will be different each time the program is run, but which is not random - the current time, for example, or the "process ID" generated by the operating system. Or both. A standard method in Perl is to seed by combining the digits of these two numbers using binary logic. And yet ... and yet ... this is not quite Random Enough. For secure applications - encrypting files, for example, in a way which is not easy for anyone else to guess how to decrypt - you need as close to Truly Random as you can get. Using the current system time, for example, is pretty easy to guess. I mean, if you're trying to break a file, you probably know when the file was created, or can make a good guess. Finding the process ID is easy too, and besides, most systems use a fixed number of process IDs that they reuse over and over. Trying five thousand possible IDs takes no time at all. The most common methods for getting close to Truly Random seeds involve much deeper tricks than that. For example, my Perl book recommends compressing the output of some system commands which change frequently (such as the list of all things which are running on a given system), getting a "checksum" number from that compressed output, and combining that with the process ID and the time. Whew. Even methods like these, though, yield fairly readily to a computer with time and algorythms to burn. They are sometimes still not Random Enough. - - - This is not just a matter of being finicky. There are plenty of cryptographic and mathematical needs which have a random number somewhere at the bottom. Some of them are important. Some of them (cryptography) are being publicly fought over in ways which will eventually affect you. Check your local newspaper. Making the final approach to Truly Random requires sort of a Zen attitude. To an extent, you can't throw more math at the problem, because adding extra algorythms doesn't necessarily make things any more random. You have to think in other directions. Simpler ones. Lava lamps, for example. Oh, yes. Think about it. Can you predict where the wax (that glop is mostly wax, yes) is going to go next? As a matter of fact, there are algorythms for predicting "turbulent flow" of this sort, but they're unholy hell. Add to this the idea of six lava lamps instead of one (adding complexity), being recorded on digital camera (adding a certain fuzziness), and mathematically crunched into a single very large number ... and you have a seed which, while maybe not Truly Random, is Random Enough to satisfy even the purists. For the moment, at least. Copyright © December 1997. All rights reserved. |
