Programming Random Numbers

[dgatwood]

ModNote: Per request of TyphoidHippo, I moved some posts from another thread to a new thread so they could continue their discussion on computer generated random numbers....

Post-secondary instructors crack me up. They need more shit to do. Or maybe they need to be required to actually work in the field a few months out of the year... or something. I once had a programming teacher who wouldn't let us use C's rand() function because "it wasn't random enough". Well.. guess what - commercial programming houses all use rand(), and commercial studios all use digital recording technology.

Your professor was right. The randomness generated by rand(3) is absolute garbage. The random results returned by rand(3) are simply not good enough for any real use. It's not that they aren't cryptographically random, but that they're so far from cryptographically random that if you're modding the value by more than about 10, the difference in probability of each possible value will be immediately obvious after just a handful of calls. It's that bad.

I used to use rand(3) for choosing a random photo out of a few thousand a few years ago, and it was instantly obvious that there were about two or three dozen photos that showed up better than 90% of the time, and that the other photos essentially never appeared at all. I swapped in a more legitimate random number generator (a call into OpenSSL, IIRC), and suddenly I almost never saw the same photo twice within a few minutes (as you would expect out of a pool of several thousand). The difference in randomness is absolutely staggering.

Heck, the man page for rand(3) in Mac OS X starts with the words "These interfaces are obsoleted by random(3)." If someone came to me with a tool that tried to be random and I saw it calling rand(), unless the tool was written before random(3) was standardized (about ten years ago), I would immediately conclude that the author was a newb. It's just way too easy to get much better random numbers.

It's not elitism to call a turd a turd.

 

[diggy_dude]

I used to use rand(3) for choosing a random photo out of a few thousand a few years ago, and it was instantly obvious that there were about two or three dozen photos that showed up better than 90% of the time, and that the other photos essentially never appeared at all.

I can vouch for this. I got much better results with the Butler-Yeats algorithm than with a native rand() when choosing random photos. Regretably, I didn't have the luxury of doing a statistical analysis of the comparative results. In my work, you just find something that yields good results as quickly as possible and move on to the next thing.

 

[TyphoidHippo]

Well, I guess without more context - my point wasn't very clear. When you just want some random thing that nobody's going to notice anything about except that it was apparently random - rand does that job just fine and it does it immediately - move on to the next problem. In my experience - this makes up about 99% of the use of an RNG. I mean... wow. I don't know how long it's been since you guys have tried a recent implementation of rand - but... it works - I know it's not truly random in any implementation, but I've used it extensively to implement all kinds of branching AI algorithms with way, way, more than 10 possibilities and shown them to audiences at GDC and other conferences and never once has anybody ever said "hey - it seems like the AI tends to do xxx more".

...sorry for the thread highjack, Rabid Pickle. This wasn't my intention...it was just something that came to mind. If you guys really want to discuss the rand thing further, I'd be happy - but let's do it in the off-topic forum or something.

edit: C++ code - 18 lines - codepad looks pretty random to me

 

[diggy_dude]

When you just want some random thing that nobody's going to notice anything about except that it was apparently random....

The problem is, the lack of randomness is readily noticeable to a causal observer after a few iterations.

 

[TyphoidHippo]

The problem is, the lack of randomness is readily noticeable to a causal observer after a few iterations.

I edited my post while you replied, sorry.

 

[diggy_dude]

I edited my post while you replied, sorry.

No worries. I shouldn't be thinking about work in the middle of the night anyway.

 

[VomitHatSteve]

I probably wouldn't respond to this thread on D v. I, but I do have opinions on random numbers!

Relevant link!

If your rand() call is that close to the surface that it's effect are immediately noticeable when using the program, it should be pretty obvious during debugging/QA if you need to change it.

If you're doing cryptography, you had better be a freaking expert on which RNG is the best.

 

[diggy_dude]

If your rand() call is that close to the surface that it's effect are immediately noticeable when using the program, it should be pretty obvious during debugging/QA if you need to change it.

It's that noticeable during coding and testing, let alone QA.

 

[TetraFish]

I know with the random function in VB it would come up with the same sequence of "random" numbers every time unless you used a seed number. So if you used something like random(now()) it would seed the random function with a number like 31445.432545 or what ever now() returned as for the date/time value. Not sure how the algorythm used that seed value but it would change it enough that you couldn't readily detect a pattern.

 

[TyphoidHippo]

I know with the random function in VB it would come up with the same sequence of "random" numbers every time unless you used a seed number. So if you used something like random(now()) it would seed the random function with a number like 31445.432545 or what ever now() returned as for the date/time value. Not sure how the algorythm used that seed value but it would change it enough that you couldn't readily detect a pattern.

I'd imagine that VB's random calls rand() internally, and the overload for seeding calls srand(seed). You can check in reflector easily enough, I'd imagine. The original discussion was about the randomness of rand in the standard C library... and actually, after re-reading dgatwood's post, and that every time he mentioned rand, he calls it with an argument of 3, I have no idea what he's even talking about - the standard C function rand() is prototyped as

int rand ( void );

and always has been, as far as I know. There is no function called "random" in standard C, and I've never programmed using Mac-specific APIs, nor did I mention them anywhere. Even if standard C used to have int rand(int), and it sucked - it's not like standard functions aren't constantly improved in their implementations (they certainly are - at least the ones from MS and GCC teams...again, I've never programmed any Mac stuff). The paste I made shows pretty well, I think, that a modern implementation of rand is quite random, even when modding by 1000, and even over a million iterations.

I'd be interested in seeing code that shows better results, and I'd promptly forward it to MS and GCC so their next releases of the CRT can include it ...and Apple, too - apparently their rand is pretty ridiculous.

 

[stevieb]

I just opened a thread at random, and ended up here. Can I play?

 

[DrCobweb]

The generation of random numbers is far too important to be left to chance.

 

[cyrano]

Interesting project from Princeton.

 

[guitaristic]

This may be one of the most intellectual/over-my-head threads I've ever read here. Due to that, I kindly bow and take my leave!

Kudos gents

 

[Sirnothingness]

Can you guys help me pick some Keno numbers?