Let’s take it easy this week. What about we generate random passwords? That should be fun, right?
I am still experimenting with hash functions, and I was toying with the Zobrist hash function that is best known for its use in chess engines. The hash function is conceptually simple: you need a large table of random numbers, indexed, in a chess application, by the position on the board of the piece and by the piece itself. To compute a hash for a whole board configuration, you simply xor all the random numbers together. The hard part is choosing the random numbers.
Suppose you want to draw randomly a number between 0 and 1, with multiple throws of a six sided dice, what would you write down on its face?
Before we go on exploring hash functions for look-up, let’s discuss their basic anatomy. This will give us some vocabulary as well as help us identify what are the important characteristics of good hash functions.
Here’s a LEGO dice-tossing machine I built.
The two complicated parts are the reduction gear train and the flaps that re-center the dice so that the machine can pick it up correctly each time.
The gear train is composed of several gear reducers, which are composed of a small gear driving a larger gear (thus many turns of the small, driving gear, are needed for the big one to make a complete rotation). Each large gear share its spindle with a small gear that drives the next stage. The gear box yields a 243:1 reduction (which is to 1). Otherwise the motor spins too fast and just, well, eject the dice from the machine.
The flaps are used to funnel the dice back in the middle of the tray, where it can be picked up again.
The next step would be to use OCR to read the dice value and see if, in the long run, the tosser is a strong number generator or if it is flawed in some way. Can’t really remember where I got the 16-sided dice, but there are some to be found online.
On a number of previous installment of this series, I’ve discussed permutations, generating uniform random points in a triangle, on a sphere, the inversion method, even recycling expensive random bits. In this entry, I will use the rejection method to generate random numbers from disjoint ranges.
For simplicity, let us consider only the uniform case, where all values are equally likely to be drawn. So instead of drawing a number from a range, say , we’re interested in the case where the set is composed from several intervals, something like . We may think of drawing uniformly from and retry if we “fall in the gaps”, that is, if we draw a number in or .
A first, it doesn’t seem like a bad plan, especially if the “holes” are rather small and easy to miss—that is, we have a good chance of hitting in an allowable range in a very few tries. For example, if the ranges we’re interested in look like and , drawing from really doesn’t sound like a good idea.
But what if we compacted the ranges?