[Chicken-hackers] Fix for Random Number Generator

[Will M. Farr]

Hello,

I noticed today that the random number generator in Chicken makes a
common, but *serious*, mistake in the use of rand().  The attached
patch (against current svn) fixes the mistake, and should improve the
quality of the random integers returned by (random <n>).

The problem lies in the way that rand() generates random numbers on
many systems.  In general, the quality of rand()-generated numbers is
not very good, but the quality of randomness in the least-significant
bits is often *much* worse than the overall quality.  For example, on
my Mac OS X 10.5 system, the man page for random() (a better version
of rand() ) says:

     The random() and srandom() functions have (almost) the same calling
     sequence and initialization properties as the rand(3) and srand(3) func-
     tions.  The difference is that rand(3) produces a much less random
     sequence -- in fact, the low dozen bits generated by rand go through a
     cyclic pattern.  All of the bits generated by random() are usable.  For
     example, `random()&01' will produce a random binary value.

Previously, Chicken used (rand() % max_value) to compute a random
number between 0 and max_value (exclusive), which access precisely the
bits of rand() which are the *least* random.  The attached patch uses
rand() and RAND_MAX to generate a double between 0.0 and 1.0
(exclusive), then multiplies by max_value, and finally converts back
to an int to generate a random number.

The Right Thing (TM) to do would probably be to adopt SRFI-27 in the
core of Chicken (the output of rand() is typically pretty bad no
matter what you do), and maybe I'll take that on some day, but for now
this is a quick fix that should improve the quality of random numbers
coming out of (random <n>) a bit.  Let me know if you need more
information, or if there's anything else I can help with in getting
this patch committed.

Thanks,
Will

Index: chicken.h
===================================================================
--- chicken.h   (revision 13799)
+++ chicken.h   (working copy)
@@ -1037,7 +1037,7 @@
                                                  C_unfix(end1) - 
C_unfix(start1) ), C_SCHEME_UNDEFINED)
 #define C_words(n)                      C_fix(C_bytestowords(C_unfix(n)))
 #define C_bytes(n)                      C_fix(C_wordstobytes(C_unfix(n)))
-#define C_random_fixnum(n)              C_fix(rand() % C_unfix(n))
+#define C_random_fixnum(n)
C_fix((int)(((double)rand())/(RAND_MAX + 1.0) * C_unfix(n)))
 #define C_randomize(n)                  (srand(C_unfix(n)), C_SCHEME_UNDEFINED)
 #define C_block_size(x)                 C_fix(C_header_size(x))
 #define C_pointer_address(x)            ((C_byte *)C_u_i_car(x))