diff options
| -rw-r--r-- | lib.c | 2 | ||||
| -rw-r--r-- | rand.c | 58 | ||||
| -rw-r--r-- | rand.h | 2 | ||||
| -rw-r--r-- | txr.1 | 60 |
4 files changed, 92 insertions, 30 deletions
@@ -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 */ @@ -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)); @@ -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); @@ -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 |