random not random

[Jim Ursetto]

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.

[Jim Ursetto]

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!

960 960 ... 961 ... 964 964 964 964 964 964 964 965 965 965 ...

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.

[Jim Ursetto]

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.

[Jim Ursetto]

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.

[felix winkelmann]

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.

[Jim Ursetto]

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.

[felix winkelmann]

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).

[felix winkelmann]

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)

[Jim Ursetto]

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.

[felix winkelmann]

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.

[Jim Ursetto]

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

[felix winkelmann]

Milestone 4.6.0 deleted

[Jim Ursetto]

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.