[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Chicken-hackers] Fix for Random Number Generator
From: |
Will M. Farr |
Subject: |
[Chicken-hackers] Fix for Random Number Generator |
Date: |
Tue, 17 Mar 2009 12:07:16 -0400 |
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))
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Chicken-hackers] Fix for Random Number Generator,
Will M. Farr <=