Summary

random not random

Metadata

Attachments

Description

So rand() is completely subpar at generating random numbers in two ways:

1. Lower bits are not random. We already work around this in the standard manner by scaling the result of a floating-point division.

2. Nearby seeds don't affect the output much.

Due to # 2, on Mac OS X we may obtain the same initial random number for a minute or more, even though it is seeded with (current-seconds):

 while :; do csi -p '(random 1000)'; sleep 5; done
 734
 734
 734
 734
 734
 209
 209

We can fix the problem on OS X by using random(3) instead of rand(3), which is present on all BSDs and on Linux.

Internally, Linux uses random() when rand() is called and some BSDs seem to as well. However, there should be no harm anyway in applying the attached patch, which affects linux and bsd.

Changes and comments

[2010-04-23 23:17:57 UTC] zbigniew attached 0001-random.diff.txt (description=#f)

[2010-04-23 23:23:02 UTC] zbigniew wrote:

However, there's still a worse problem. On Windows and Solaris, rand() returns a number between 0 and 32767. This means that in N trials of (random 100000000), you can only ever get 32768 unique numbers.

Furthermore Windows (XP) seems to exhibit the same problem as OS X where it returns the same initial random number for many seconds, and furthermore, the returned numbers are sequential!

 
 Unfortunately to fix this you start getting into OS-specific functions like rand_s() on Windows (needs XP or higher) and drand48(3) on Solaris.

[2010-04-23 23:29:54 UTC] zbigniew wrote:

So I don't know how hard you want to try to fix randomness on weird platforms. The 32768 limit seems important but there is no easy fix.

One thing tangentially related is it might be interesting to hash the value of current-seconds and/or hash in the value of current-milliseconds to provide a little more perceived randomness at startup time.

[2010-04-23 23:33:33 UTC] zbigniew wrote:

It looks like I forgot to modify "random-seed" in extras.scm, which uses srand.

However, shouldn't random-seed be removed or made into an alias to randomize? It's exactly the same call as randomize, but it uses srand directly instead of C_randomize.

OK, I'm done.

[2010-04-26 15:29:35 UTC] felix removed owner

[2010-04-26 15:29:35 UTC] felix changed component from unknown to core libraries

[2010-04-26 15:29:35 UTC] felix wrote:

We had this already: "portable" functions for doing random numbers where in the end not portable at all...

I suggest staying with rand(3) (possibly hashed) and provide better random number generators as eggs. I will check wether `random-seed` can be removed.

[2010-04-26 20:36:59 UTC] zbigniew wrote:

The behavior of rand(3) is so poor and inconsistent across systems that it may be better then to simply remove (random) from the core than to pretend it actually works.

In the meantime, I updated man/4/Unit extras with warnings about the quality of random's randomness.

[2010-08-02 14:43:51 UTC] felix wrote:

I still believe that in many cases the admittedly insufficient `rand(3)` is enough. Providing more adequate random-number generators should be done by extensions (see, for example, `random-mtzig`).

[2010-08-02 14:43:51 UTC] felix changed status from new to closed

[2010-08-02 14:43:51 UTC] felix set resolution to worksforme

[2010-08-02 22:23:18 UTC] felix wrote:

Replying to felix: > I still believe that in many cases the admittedly insufficient `rand(3)` is enough. Providing more adequate random-number generators should be done by extensions (see, for example, `random-mtzig`).

(and srfi-27, of course)

[2010-08-02 23:35:57 UTC] zbigniew wrote:

I still believe random() should be used when available, and that rand() about as useful as generating the numbers 0, 1, 2, ...

(random) should have been called (rand) instead.

[2010-08-03 00:55:04 UTC] felix wrote:

Replying to zbigniew: > I still believe random() should be used when available, and that rand() about as useful as generating the numbers 0, 1, 2, ...

The problem is that it is nearly impossible to figure out where this is supported and where not. Kon already put an awful lot of work into porting, the last time this was tried and we found out merely by trial and error that `random/srandom` is (for example) not available on older NetBSD systems and Gentoo Linux. There has been enough time wasted with this.

There are two types of randomness:

1. Getting some arbitrary number, nevermind which one

2. Getting high-quality random numbers

chicken's `random` provides (1), eggs provide (2).

Could you provide a small, portable C implementation (BSD licensed or compatible) of an efficient and high-quality random number generator? That would be the best solution.

[2010-08-03 01:45:25 UTC] zbigniew wrote:

You're right, I apologize. I should shut up and code.

[2011-04-04 08:31:00 UTC] felix removed milestone 4.6.0

[2011-04-04 08:31:00 UTC] felix wrote:

Milestone 4.6.0 deleted

[2011-07-08 18:52:58 UTC] zbigniew wrote:

This should be addressed now with the http://api.call-cc.org/doc/random-bsd egg, which includes a "small, portable C implementation (BSD licensed or compatible) of an efficient and high-quality random number generator", that I ripped from FreeBSD.