Opened 9 years ago

Closed 9 years ago

Last modified 8 years ago

#218 closed defect (worksforme)

random not random

Reported by: Jim Ursetto Owned by:
Priority: minor Milestone:
Component: core libraries Version:
Keywords: Cc:
Estimated difficulty:

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

Attachments (1)

0001-random.diff.txt (978 bytes) - added by Jim Ursetto 9 years ago.

Download all attachments as: .zip

Change History (13)

Changed 9 years ago by Jim Ursetto

Attachment: 0001-random.diff.txt added

comment:1 Changed 9 years ago by 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.

comment:2 Changed 9 years ago by 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.

comment:3 Changed 9 years ago by 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.

comment:4 Changed 9 years ago by felix winkelmann

Component: unknowncore libraries

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.

comment:5 Changed 9 years ago by 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.

comment:6 Changed 9 years ago by felix winkelmann

Resolution: worksforme
Status: newclosed

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

comment:7 in reply to:  6 Changed 9 years ago by 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)

comment:8 Changed 9 years ago by 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.

comment:9 in reply to:  8 Changed 9 years ago by 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
  1. 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.

comment:10 Changed 9 years ago by Jim Ursetto

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

comment:11 Changed 8 years ago by felix winkelmann

Milestone: 4.6.0

Milestone 4.6.0 deleted

comment:12 Changed 8 years ago by 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.

Note: See TracTickets for help on using tickets.