summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--lib.c2
-rw-r--r--rand.c58
-rw-r--r--rand.h2
-rw-r--r--txr.160
4 files changed, 92 insertions, 30 deletions
diff --git a/lib.c b/lib.c
index 1256314f..1d41ea6b 100644
--- a/lib.c
+++ b/lib.c
@@ -7979,7 +7979,7 @@ val copy(val seq)
if (seq->co.cls == hash_s)
return copy_hash(seq);
if (seq->co.cls == random_state_s)
- return make_random_state(seq);
+ return make_random_state(seq, nil);
if (structp(seq))
return copy_struct(seq);
/* fallthrough */
diff --git a/rand.c b/rand.c
index 6cdd937d..f0c10dae 100644
--- a/rand.c
+++ b/rand.c
@@ -41,6 +41,8 @@
#include "rand.h"
#include "eval.h"
+#define random_warmup (deref(lookup_var_l(nil, random_warmup_s)))
+
#if SIZEOF_INT == 4
typedef unsigned int rand32_t;
#elif SIZEOF_LONG == 4
@@ -56,7 +58,7 @@ struct rand_state {
unsigned cur;
};
-val random_state_s, random_state_var_s;
+val random_state_s, random_state_var_s, random_warmup_s;
static struct cobj_ops random_state_ops = cobj_ops_init(eq,
cobj_print_op,
@@ -99,17 +101,18 @@ static rand32_t rand32(struct rand_state *r)
return ns15;
}
-val make_random_state(val seed)
+val make_random_state(val seed, val warmup)
{
val rs = make_state();
- int i, copy = 0;
+ int i = 0;
struct rand_state *r = coerce(struct rand_state *,
cobj_handle(rs, random_state_s));
seed = default_bool_arg(seed);
+ warmup = default_bool_arg(warmup);
if (bignump(seed)) {
- int i, dig, bit;
+ int dig, bit;
mp_int *m = mp(seed);
for (i = 0, dig = 0, bit = 0; i < 16 && dig < m->used; i++) {
@@ -118,21 +121,15 @@ val make_random_state(val seed)
if (bit >= MP_DIGIT_BIT)
dig++, bit = 0;
}
-
- while (i > 0 && !r->state[i - 1])
- i--;
-
- if (i < 16)
- memset(r->state + i, 0xAA, sizeof r->state - i * sizeof r->state[0]);
} else if (fixnump(seed)) {
cnum s = c_num(seed) & NUM_MAX;
- memset(r->state, 0xAA, sizeof r->state);
r->state[0] = s & 0xFFFFFFFFul;
+ i = 1;
#if SIZEOF_PTR == 8
s >>= 32;
- if (s)
- r->state[1] = s & 0xFFFFFFFFul;
+ r->state[1] = s & 0xFFFFFFFFul;
+ i = 2;
#elif SIZEOF_PTR > 8
#error port me!
#endif
@@ -142,16 +139,16 @@ val make_random_state(val seed)
r->state[1] = convert(rand32_t, c_num(cdr(time)));
#if HAVE_UNISTD_H
r->state[2] = convert(rand32_t, getpid());
+ i = 3;
+#else
+ i = 2;
#endif
- memset(r->state + 3, 0xAA, sizeof r->state - 3 * sizeof r->state[0]);
} else if (random_state_p(seed)) {
struct rand_state *rseed = coerce(struct rand_state *,
cobj_handle(seed, random_state_s));
*r = *rseed;
- copy = 1;
+ return rs;
} else if (vectorp(seed)) {
- int i;
-
if (length(seed) < num_fast(17))
uw_throwf(error_s, lit("make-random-state: vector ~s too short"),
seed, nao);
@@ -160,15 +157,25 @@ val make_random_state(val seed)
r->state[i] = c_uint_ptr_num(seed->v.vec[i]);
r->cur = c_num(seed->v.vec[i]);
- copy = 1;
+ return rs;
} else {
uw_throwf(error_s, lit("make-random-state: seed ~s is not a number"),
seed, nao);
}
- if (!copy) {
- r->cur = 0;
- for (i = 0; i < 8; i++)
+ while (i > 0 && r->state[i - 1] == 0)
+ i--;
+
+ for (; i < 16; i++)
+ r->state[i] = 0xAAAAAAAAul;
+
+ r->cur = 0;
+
+ {
+ uses_or2;
+ cnum wu = c_num(or2(warmup, random_warmup));
+
+ for (i = 0; i < wu; i++)
(void) rand32(r);
}
@@ -289,7 +296,7 @@ void rand_compat_fixup(int compat_ver)
if (compat_ver <= 114) {
loc l = lookup_var_l(nil, random_state_var_s);
random_state_s = random_state_var_s;
- set(l, make_random_state(num_fast(42)));
+ set(l, make_random_state(num_fast(42), num_fast(8)));
}
}
@@ -297,10 +304,13 @@ void rand_init(void)
{
random_state_var_s = intern(lit("*random-state*"), user_package);
random_state_s = intern(lit("random-state"), user_package);
- reg_var(random_state_var_s, make_random_state(num_fast(42)));
+ random_warmup_s = intern(lit("*random-warmup*"), user_package);
+
+ reg_var(random_state_var_s, make_random_state(num_fast(42), num_fast(8)));
+ reg_var(random_warmup_s, num_fast(8));
reg_fun(intern(lit("make-random-state"), user_package),
- func_n1o(make_random_state, 0));
+ func_n2o(make_random_state, 0));
reg_fun(intern(lit("random-state-get-vec"), user_package),
func_n1o(random_state_get_vec, 0));
reg_fun(intern(lit("random-state-p"), user_package), func_n1(random_state_p));
diff --git a/rand.h b/rand.h
index 97dc4bc7..62d726cb 100644
--- a/rand.h
+++ b/rand.h
@@ -26,7 +26,7 @@
#define random_state (deref(lookup_var_l(nil, random_state_var_s)))
extern val random_state_s, random_state_var_s;
-val make_random_state(val seed);
+val make_random_state(val seed, val warmup);
val random_state_get_vec(val state);
val random_state_p(val obj);
val random_fixnum(val state);
diff --git a/txr.1 b/txr.1
index e018123d..41b53314 100644
--- a/txr.1
+++ b/txr.1
@@ -35526,9 +35526,47 @@ a newly created random state object, which is produced as if by
the call
.codn "(make-random-state 42)" .
+.coNP Special variable @ *random-warmup*
+.desc
+The
+.code *random-warmup*
+special variable specifies the value which is used by
+.code make-random-state
+in place of a missing
+.meta warmup-period
+argument.
+
+To "warm up" a pseudo-random number generator (PRNG) means to obtain some
+values from it which are discarded, prior to use. The number of values
+discarded is the
+.IR "warm-up period" .
+
+The WELL PRNG used in \*(TX produces 32-bit values, natively. Thus each
+warm-up iteration retrieves and discards a 32-bit value. The PRNG has
+a state space consisting of a vector of sixteen 32-bit words, making
+the state space 4096 bits wide.
+
+Warm up is required because PRNG-s, in particular PRNG-s with large state
+spaces and long periods, produce fairly predictable sequences of values in the
+beginning, before transitioning into chaotic behavior. This problem is worse
+for low complexity seeds, such as small integer values.
+
+.TP* Notes:
+
+The default value of .code *random-warmup* is only 8. This is insufficient to
+ensure good initial PRNG behavior for seeds even as large as 64 bits or more.
+That is to say, even if as many as eight bytes' worth of true random bits are
+used as the seed, the PRNG will exhibit predictable behaviors, and a poor
+distribution of values.
+
+Applications which critically depend on good PRNG behavior should choose
+large warm-up periods into the hundreds or thousands of iterations.
+If a small warm-up period is used, it is recommended to use larger seeds
+which initialize more of the 4096 bit state space.
+
.coNP Function @ make-random-state
.synb
-.mets (make-random-state <> [ seed ])
+.mets (make-random-state << [ seed <> [ warmup-period ])
.syne
.desc
The
@@ -35546,7 +35584,7 @@ to the function
Note that the sign of the seed is ignored, so that negative seed
values are equivalent to their additive inverses.
-If the seed is not specified, then
+If seed is not specified, then
.code make-random-state
produces a seed based
on some information in the process environment, such as current
@@ -35573,6 +35611,20 @@ representation by the
.code random-state-get-vec
function.
+The
+.meta warm-up-period
+argument specifies the number of values which are immediately obtained and
+discarded from the newly-seeded generator before it is returned.
+Warm-up is not performed when
+.meta seed
+is an existing random state object, and this argument is ignored in that
+case. If the parameter is required, but the argument is missing, then
+the value of the
+.code *random-warmup*
+special variable is used. This variable has a default value which may be too
+small for serious applications of pseudo-random numbers; see the Notes under
+.codn *random-warmup* .
+
.coNP Function @ random-state-p
.synb
.mets (random-state-p << obj )
@@ -35612,8 +35664,8 @@ is used.
.desc
All three functions produce pseudo-random numbers, which are positive integers.
-The numbers are obtained from a WELLS 512 pseudo-random number generator, whose
-state is stored in the random state object.
+The numbers are obtained from a WELL 512 PRNG, whose state is stored in the
+random state object.
The
.code random-fixnum