Random number challenge

Hans Fugal hans at fugal.net
Thu Jun 12 16:16:00 MDT 2008


Hans Fugal wrote:
> Andrew Jorgensen wrote:
>> This comes up every month at PLUG (for door prizes) so I thought I'd 
>> ask here.  What's an easy to remember way to generate a random number 
>> between 1 and some given number.  Language doesn't matter so long as 
>> the code is easy enough for someone to remember the entire thing and 
>> type it up at the drop of a hat.
>>
>> Go, lazylist, go!
> 
> $ irb
>  >> rand <your number here>
> <your random number here>
> 
> Add 1 in your head if you want between 1 and N instead of 0 and N-1. Or 
> do you mean a way without a computer? In that case grab lg(N) people and 
> have them each flip a coin, repeat if you get a number bigger than N. 
> Expected number of trials is between 1 and 2.
> 
> 

After reading the other posts (I didn't want to cheat) I want to point 
out that irb is the simplest and easiest to remember that we've seen, 
and quells Stuart's paranoia to a reasonable degree (well, to a 
reasonable person anyway):

Ruby's PRNG is a Mersenne Twister with a period of 2**19937-1. This 
algorithm is generally considered Pretty Darn Good. It is automatically 
seeded using a combination of the time, the process id, and a sequence 
number (not just the PID, nor just the time). Cryptographically secure? 
Probably not. But even Jayce^ wouldn't begrudge a Fugal his prize, I think.

If you're truly concerned about true randomness, use the coin flip 
method (note parallel coin flips makes it very very hard to stage this 
with biased coins if you get coins from various people).

If /dev/random is the only source of randomness you trust,

$ head -c 16 /dev/random | xxd
0000000: 278a 5606 3672 164d d3d9 a3e0 131d 49f5  '.V.6r.M......I.

Pick the first nibble/byte greater than 0 and less than or equal to N.

I'm sure the mysterious Fugal bias is related to that statistics trick 
where you are almost guaranteed to find two people with the same 
birthday in a room with at least N people. I don't know exactly what 
that means but I hope it means I get two birthdays.

-- 
Hans Fugal ; http://hans.fugal.net

There's nothing remarkable about it. All one has to do is hit the
right keys at the right time and the instrument plays itself.
     -- Johann Sebastian Bach



More information about the PLUG mailing list