summaryrefslogtreecommitdiff
path: root/random.c
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2005-01-04 17:38:39 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2005-01-04 17:38:39 +0000
commit0ce3a808c2a5228e4ca930fac70c2559de7bd015 (patch)
treeb67de4c8cf661e9e4c3e2f80eb0a62ab5c968974 /random.c
parent89c053113d7b741da64f3187d7a6c27a1d524f8b (diff)
* random.c (init_by_array): imported from mt19937ar-cok.tgz.
(genrand_int32): ditto. (genrand_real): replaced with genrand_res53 in mt19937ar-cok. (rand_init): support bignum for longer seed. (random_seed): generate longer seed. (make_mask): new function. (limited_rand): ditto. (limited_big_rand): ditto. (rb_f_rand): call limited_rand and limited_big_rand. [ruby-dev:25403] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_8@7723 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'random.c')
-rw-r--r--random.c253
1 files changed, 216 insertions, 37 deletions
diff --git a/random.c b/random.c
index 3f34b04..4c86b55 100644
--- a/random.c
+++ b/random.c
@@ -92,6 +92,37 @@ init_genrand(s)
left = 1; initf = 1;
}
+/* initialize by an array with array-length */
+/* init_key is the array for initializing keys */
+/* key_length is its length */
+/* slight change for C++, 2004/2/26 */
+static void
+init_by_array(unsigned long init_key[], int key_length)
+{
+ int i, j, k;
+ init_genrand(19650218UL);
+ i=1; j=0;
+ k = (N>key_length ? N : key_length);
+ for (; k; k--) {
+ state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1664525UL))
+ + init_key[j] + j; /* non linear */
+ state[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++; j++;
+ if (i>=N) { state[0] = state[N-1]; i=1; }
+ if (j>=key_length) j=0;
+ }
+ for (k=N-1; k; k--) {
+ state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1566083941UL))
+ - i; /* non linear */
+ state[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++;
+ if (i>=N) { state[0] = state[N-1]; i=1; }
+ }
+
+ state[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
+ left = 1; initf = 1;
+}
+
static void
next_state()
{
@@ -114,9 +145,9 @@ next_state()
*p = p[M-N] ^ TWIST(p[0], state[0]);
}
-/* generates a random number on [0,1)-real-interval */
-static double
-genrand_real()
+/* generates a random number on [0,0xffffffff]-interval */
+static unsigned long
+genrand_int32(void)
{
unsigned long y;
@@ -129,10 +160,18 @@ genrand_real()
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
- return (double)y * (1.0/4294967296.0);
- /* divided by 2^32 */
+ return y;
}
+/* generates a random number on [0,1) with 53-bit resolution*/
+static double
+genrand_real(void)
+{
+ unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6;
+ return(a*67108864.0+b)*(1.0/9007199254740992.0);
+}
+/* These real versions are due to Isaku Wada, 2002/01/09 added */
+
#undef N
#undef M
@@ -151,36 +190,91 @@ genrand_real()
#endif
static int first = 1;
+static VALUE saved_seed = INT2FIX(0);
-static int
-rand_init(seed)
- unsigned long seed;
+static VALUE
+rand_init(vseed)
+ VALUE vseed;
{
- static unsigned long saved_seed;
- unsigned long old;
+ volatile VALUE seed;
+ VALUE old;
+ long len;
+ unsigned long *buf;
+ seed = rb_to_int(vseed);
+ switch (TYPE(seed)) {
+ case T_FIXNUM:
+ len = sizeof(VALUE);
+ break;
+ case T_BIGNUM:
+ len = RBIGNUM(seed)->len * SIZEOF_BDIGITS;
+ if (len == 0)
+ len = 4;
+ break;
+ default:
+ rb_raise(rb_eTypeError, "failed to convert %s into Integer",
+ rb_obj_classname(vseed));
+ }
+ len = ((len + 3) / 4); /* round up to 32bits */
+ buf = ALLOCA_N(long, len); /* allocate longs for init_by_array */
+ memset(buf, 0, len * sizeof(long));
+ if (FIXNUM_P(seed)) {
+ buf[0] = FIX2ULONG(seed) & 0xffffffff;
+#if SIZEOF_LONG > 4
+ buf[1] = FIX2ULONG(seed) >> 32;
+#endif
+ }
+ else {
+ int i, j;
+ for (i = RBIGNUM(seed)->len-1; 0 <= i; i--) {
+ j = i * SIZEOF_BDIGITS / 4;
+#if SIZEOF_BDIGITS < SIZEOF_LONG
+ buf[j] = buf[j] << (SIZEOF_BDIGITS * 8);
+#endif
+ buf[j] |= ((BDIGIT *)RBIGNUM(seed)->digits)[i];
+ }
+ }
+ while (1 < len && buf[len-1] == 0) {
+ len--;
+ }
+ if (len <= 1) {
+ init_genrand(buf[0]);
+ }
+ else {
+ if (buf[len-1] == 1) /* remove leading-zero-guard */
+ len--;
+ init_by_array(buf, len);
+ }
first = 0;
- init_genrand(seed);
old = saved_seed;
saved_seed = seed;
return old;
}
-static unsigned long
+static VALUE
random_seed()
{
static int n = 0;
struct timeval tv;
- unsigned long result;
int fd;
- unsigned long buf;
struct stat statbuf;
+ BDIGIT *digits;
+ unsigned long *seed;
+ NEWOBJ(big, struct RBignum);
+ OBJSETUP(big, rb_cBignum, T_BIGNUM);
+ big->sign = 1;
+ big->len = sizeof(long) * 8 / SIZEOF_BDIGITS + 1;
+ digits = big->digits = ALLOC_N(BDIGIT, big->len);
+ seed = (unsigned long *)big->digits;
- gettimeofday(&tv, 0);
- result = tv.tv_sec ^ tv.tv_usec ^ getpid() ^ n++;
+ memset(digits, 0, big->len * SIZEOF_BDIGITS);
- result += (unsigned long)&result;
+ gettimeofday(&tv, 0);
+ seed[0] = tv.tv_usec;
+ seed[1] = tv.tv_sec;
+ seed[2] = getpid() ^ (n++ << 16);
+ seed[3] = (unsigned long)&seed;
#ifdef S_ISCHR
if ((fd = open("/dev/urandom", O_RDONLY|O_NONBLOCK
@@ -192,14 +286,16 @@ random_seed()
#endif
)) >= 0) {
if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) {
- read(fd, &buf, sizeof(buf));
- result ^= buf;
+ read(fd, &seed[4], 4 * sizeof(*seed));
}
close(fd);
}
#endif
- return result;
+ /* set leading-zero-guard if need. */
+ digits[big->len-1] = digits[big->len-2] <= 1 ? 1 : 0;
+
+ return rb_big_norm((VALUE)big);
}
/*
@@ -222,19 +318,94 @@ rb_f_srand(argc, argv, obj)
VALUE *argv;
VALUE obj;
{
- VALUE sd;
- unsigned long seed, old;
+ VALUE seed, old;
rb_secure(4);
- if (rb_scan_args(argc, argv, "01", &sd) == 0) {
+ if (rb_scan_args(argc, argv, "01", &seed) == 0) {
seed = random_seed();
}
- else {
- seed = NUM2ULONG(sd);
- }
old = rand_init(seed);
- return ULONG2NUM(old);
+ return old;
+}
+
+static unsigned long
+make_mask(unsigned long x)
+{
+ x = x | x >> 1;
+ x = x | x >> 2;
+ x = x | x >> 4;
+ x = x | x >> 8;
+ x = x | x >> 16;
+#if 4 < SIZEOF_LONG
+ x = x | x >> 32;
+#endif
+ return x;
+}
+
+static unsigned long
+limited_rand(unsigned long limit)
+{
+ unsigned long mask = make_mask(limit);
+ int i;
+ unsigned long val;
+
+ retry:
+ val = 0;
+ for (i = SIZEOF_LONG/4-1; 0 <= i; i--) {
+ if (mask >> (i * 32)) {
+ val |= genrand_int32() << (i * 32);
+ val &= mask;
+ if (limit < val)
+ goto retry;
+ }
+ }
+ return val;
+}
+
+static VALUE
+limited_big_rand(struct RBignum *limit)
+{
+ unsigned long mask, lim, rnd;
+ struct RBignum *val;
+ int i, len, boundary;
+
+ len = (limit->len * SIZEOF_BDIGITS + 3) / 4;
+ val = (struct RBignum *)rb_big_clone((VALUE)limit);
+ val->sign = 1;
+#if SIZEOF_BDIGITS == 2
+# define BIG_GET32(big,i) (((BDIGIT *)(big)->digits)[(i)/2] | \
+ ((i)/2+1 < (big)->len ? (((BDIGIT *)(big)->digits)[(i)/2+1] << 16)
+ : 0))
+# define BIG_SET32(big,i,d) ((((BDIGIT *)(big)->digits)[(i)/2] = (d) & 0xffff), \
+ ((i)/2+1 < (big)->len ? (((BDIGIT *)(big)->digits)[(i)/2+1] = (d) >> 16) \
+ : 0))
+#else
+ /* SIZEOF_BDIGITS == 4 */
+# define BIG_GET32(big,i) (((BDIGIT *)(big)->digits)[i])
+# define BIG_SET32(big,i,d) (((BDIGIT *)(big)->digits)[i] = (d))
+#endif
+ retry:
+ mask = 0;
+ boundary = 1;
+ for (i = len-1; 0 <= i; i--) {
+ lim = BIG_GET32(limit, i);
+ mask = mask ? 0xffffffff : make_mask(lim);
+ if (mask) {
+ rnd = genrand_int32() & mask;
+ if (boundary) {
+ if (lim < rnd)
+ goto retry;
+ if (rnd < lim)
+ boundary = 0;
+ }
+ }
+ else {
+ rnd = 0;
+ }
+ BIG_SET32(val, i, rnd);
+ }
+ return rb_big_norm((VALUE)val);
}
/*
@@ -276,18 +447,26 @@ rb_f_rand(argc, argv, obj)
max = (long)RFLOAT(vmax)->value;
break;
}
- vmax = rb_dbl2big(RFLOAT(vmax)->value);
+ if (RFLOAT(vmax)->value < 0)
+ vmax = rb_dbl2big(-RFLOAT(vmax)->value);
+ else
+ vmax = rb_dbl2big(RFLOAT(vmax)->value);
/* fall through */
case T_BIGNUM:
bignum:
{
- long len = RBIGNUM(vmax)->len;
- double *buf = ALLOCA_N(double, len);
-
- while (len--) {
- buf[len] = genrand_real();
- }
- return rb_big_rand(vmax, buf);
+ struct RBignum *limit = (struct RBignum *)vmax;
+ if (!limit->sign) {
+ limit = (struct RBignum *)rb_big_clone(vmax);
+ limit->sign = 1;
+ }
+ limit = (struct RBignum *)rb_big_minus((VALUE)limit, INT2FIX(1));
+ if (FIXNUM_P((VALUE)limit)) {
+ if (FIX2LONG((VALUE)limit) == -1)
+ return rb_float_new(genrand_real());
+ return LONG2NUM(limited_rand(FIX2LONG((VALUE)limit)));
+ }
+ return limited_big_rand(limit);
}
case T_NIL:
max = 0;
@@ -304,8 +483,7 @@ rb_f_rand(argc, argv, obj)
return rb_float_new(genrand_real());
}
if (max < 0) max = -max;
- val = max*genrand_real();
-
+ val = limited_rand(max-1);
return LONG2NUM(val);
}
@@ -314,4 +492,5 @@ Init_Random()
{
rb_define_global_function("srand", rb_f_srand, -1);
rb_define_global_function("rand", rb_f_rand, -1);
+ rb_global_variable(&saved_seed);
}