r4nd0m pa$$w0rd

March 14, 2017

Let’s take it easy this week. What about we generate random passwords? That should be fun, right?


Read the rest of this entry »

Making a good random table

April 5, 2016

I am still experimenting with hash functions, and I was toying with the Zobrist hash function[1] 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.


Read the rest of this entry »

Real dice.

March 1, 2016

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?


Read the rest of this entry »

The anatomy of hash functions (Hash functions, part II)

October 6, 2015

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.


Read the rest of this entry »

Hash Functions (Part I)

September 29, 2015

Hash tables are a great way of ensuring O(1) access to your data. Well, it does, but as long as the hash function is good.


But what exactly makes a hash function a good hash function?

Read the rest of this entry »

The Tosser

March 10, 2015

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 3^5 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.

Drawing Random Numbers from Disjoint Ranges (Generating Random Sequences V)

March 20, 2012

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 x from a range, say [1,10], we’re interested in the case where the set is composed from several intervals, something like [1,10] \cup [20,30] \cup [40,50]. We may think of drawing uniformly from [1,50] and retry if we “fall in the gaps”, that is, if we draw a number in [11,19] or [31,39].

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 [1,10] and [95,100], drawing from [1,100] really doesn’t sound like a good idea.

But what if we compacted the ranges?

Read the rest of this entry »