diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2016-04-28 21:40:21 -0700 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2016-04-28 21:40:21 -0700 |
| commit | 07767785007f3d8d951736fb676778a6744e56b4 (patch) | |
| tree | 1a0787db9badbe75bc1acf1e0b205234929d265f | |
| parent | 49476d06993fd9df7d1e7ebe94ca508226ffa1f5 (diff) | |
| download | txr-07767785007f3d8d951736fb676778a6744e56b4.tar.gz txr-07767785007f3d8d951736fb676778a6744e56b4.tar.bz2 txr-07767785007f3d8d951736fb676778a6744e56b4.zip | |
Use random padding in PRNG rather than 0xAA.
The purpose is to eliminate any biases in
the PRNG arising out of the regularity of that pattern, so
that the behavior of successive values is good from the
beginning.
This doesn't solve the problem that a short warm-up period
leads to a poor distribution of initial values relative to the
seed space. In other words, that similar seeds lead to
initially similar sequences.
* rand.c (rand_tab): New static array.
(make_random_state): Set uninitialized parts of state from the
corresponding elements in rand_tab, rather than to the
0xAAAAAAAA values.
(rand_compat_fixup): In 139 compatibility mode, clobber
rand_tab with 0xAA bytes.
* tests/013/maze.expected: Updated.
* txr.1: Added some PRNG implementation notes, and
also compatibility notes.
| -rw-r--r-- | rand.c | 16 | ||||
| -rw-r--r-- | tests/013/maze.expected | 118 | ||||
| -rw-r--r-- | txr.1 | 25 |
3 files changed, 97 insertions, 62 deletions
@@ -66,6 +66,14 @@ static struct cobj_ops random_state_ops = cobj_ops_init(eq, cobj_mark_op, cobj_hash_op); +/* Source: bits from /dev/random on a Linux server */ +static rand32_t rand_tab[16] = { + 0x2C272ED6U, 0x4DBD5D69U, 0xC5482819U, 0x142AFCDEU, + 0xF7ABAEB0U, 0x454B47F1U, 0xFC85D2ADU, 0x1A9DB177U, + 0x2619231BU, 0x6B678AE8U, 0xAC450E78U, 0xA0A96B1CU, + 0x88A74E05U, 0xC1CBAEC2U, 0x8170BEADU, 0x29FAF776U +}; + static val make_state(void) { struct rand_state *r = coerce(struct rand_state *, chk_malloc(sizeof *r)); @@ -167,7 +175,7 @@ val make_random_state(val seed, val warmup) i--; for (; i < 16; i++) - r->state[i] = 0xAAAAAAAAul; + r->state[i] = rand_tab[i]; r->cur = 0; @@ -293,9 +301,11 @@ val rnd(val modulus, val state) void rand_compat_fixup(int compat_ver) { - if (compat_ver <= 114) { + if (compat_ver <= 139) { loc l = lookup_var_l(nil, random_state_var_s); - random_state_s = random_state_var_s; + memset(rand_tab, 0xAA, sizeof rand_tab); + if (compat_ver <= 114) + random_state_s = random_state_var_s; set(l, make_random_state(num_fast(42), num_fast(8))); } } diff --git a/tests/013/maze.expected b/tests/013/maze.expected index e3cbbf80..b9c26ae0 100644 --- a/tests/013/maze.expected +++ b/tests/013/maze.expected @@ -1,61 +1,61 @@ + +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ -| | | | | | | | | -| | | | | | | | | -+ + + + +----+ + + + +----+ + +----+----+ + + +----+ +----+ -| | | | | | | | | | | | -| | | | | | | | | | | | -+----+----+----+----+ + +----+----+----+----+----+ +----+ + +----+ +----+----+ + -| | | | | | | | | -| | | | | | | | | -+ +----+ + + + +----+ +----+----+ +----+ + +----+ +----+ +----+ + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+----+----+ + +----+----+ +----+ + + + +----+----+----+ +----+ -| | | | | | | | | | | -| | | | | | | | | | | -+----+----+ + + +----+ + +----+----+ + + +----+----+----+ + + + + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+ + +----+----+----+ + + + +----+ +----+ + +----+ + + + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ + +----+ + +----+ +----+----+ +----+ + + +----+----+ +----+----+----+ -| | | | | | | | | | | | -| | | | | | | | | | | | -+ +----+ +----+----+ +----+ + + + +----+ + +----+----+----+ + + + -| | | | | | | | | | | | -| | | | | | | | | | | | -+ + +----+ + +----+ + +----+----+----+ +----+----+ +----+ + + + + -| | | | | | | | | | | | | | -| | | | | | | | | | | | | | -+----+ + + +----+ +----+----+ +----+ + + + +----+----+ +----+----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+ +----+----+----+ +----+----+ +----+ + + + +----+----+ + + +----+----+ -| | | | | | | | -| | | | | | | | -+ +----+ +----+----+----+----+----+ +----+----+ + +----+----+----+----+----+----+ + -| | | | | | | | | | -| | | | | | | | | | -+ + +----+ + +----+ + +----+----+----+----+ + +----+ +----+ + +----+ -| | | | | | | | | | | -| | | | | | | | | | | -+ +----+ +----+----+ +----+ +----+----+ + +----+----+ +----+ +----+----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+----+----+ + + + + +----+ +----+----+----+ + + +----+----+----+ +----+ -| | | | | | | | | | -| | | | | | | | | | -+ +----+----+ +----+----+----+----+----+----+ + +----+----+----+ +----+ + +----+ -| | | | | | | | | -| | | | | | | | | -+----+ + + +----+ + +----+----+----+ +----+ + + +----+----+ +----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+ +----+ +----+----+----+----+----+----+ + +----+----+----+ + +----+----+----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+ +----+----+----+ + +----+ +----+ +----+----+ + + + + + + + + -| | | | | | | -| | | | | | | +| | | | | | | | | +| | | | | | | | | ++----+ + +----+ + + + + + +----+----+ + +----+----+ +----+ + + +| | | | | | | | | | | | | | +| | | | | | | | | | | | | | ++ +----+ +----+----+----+ +----+----+ + + + + + + + + +----+ + +| | | | | | | | | +| | | | | | | | | ++----+----+----+----+----+ +----+ +----+----+----+ +----+ + +----+----+----+ +----+ +| | | | | | | | | | +| | | | | | | | | | ++ + +----+----+----+----+ +----+----+ + +----+ + + +----+----+ +----+ + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ + + + +----+ + + + + + + +----+----+ +----+ + +----+----+ +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++----+----+ +----+ + + +----+----+----+ +----+----+ +----+ +----+----+ + + +| | | | | | | | | | +| | | | | | | | | | ++ +----+----+ +----+ +----+ +----+ +----+ +----+----+ + + +----+----+ + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++----+ + +----+ + + +----+ +----+ +----+ + +----+ + +----+ + + +| | | | | | | | | | | | +| | | | | | | | | | | | ++ +----+----+ + + +----+ + + +----+ +----+----+ +----+----+----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++----+----+ +----+----+----+ + + + + + +----+ +----+ + + + +----+ +| | | | | | | | | | | | | | | +| | | | | | | | | | | | | | | ++ + + + + +----+----+ + + + +----+ +----+----+----+----+ + + + +| | | | | | | | | | | | +| | | | | | | | | | | | ++----+ + + +----+----+ + +----+----+----+ +----+----+ +----+----+ +----+ + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ +----+ + +----+ + + +----+ + + + + +----+ + +----+ + + +| | | | | | | | | | | | | | +| | | | | | | | | | | | | | ++ +----+----+ + +----+ + + +----+ +----+----+ +----+ + + +----+ + +| | | | | | | | | | | | +| | | | | | | | | | | | ++----+ + + +----+ +----+----+ +----+----+----+----+----+ + + +----+----+ + +| | | | | | | | | | +| | | | | | | | | | ++ + +----+----+ +----+ + +----+ +----+----+ + + + +----+ + + + +| | | | | | | | | | | | | | +| | | | | | | | | | | | | | ++ + +----+----+----+ + +----+ +----+----+ + + + +----+----+----+ + + +| | | | | | | | | | | | +| | | | | | | | | | | | ++ +----+ + + +----+----+----+ +----+----+ + +----+----+ + + + +----+ +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ +----+----+ +----+ +----+----+ + + +----+----+ + +----+ + +----+ + +| | | | | | +| | | | | | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ + @@ -35551,6 +35551,11 @@ 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. +The sequences are predictable in two ways. Firstly, some initial values +extracted from the PRNG may exhibit patterns ("problem 1"). Secondly, the initial values +from sequences produced from similar seeds (for instance consecutive integers) +may be similar or identical ("problem 2"). + .TP* Notes: The default value of .code *random-warmup* is only 8. This is insufficient to @@ -35564,6 +35569,17 @@ 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. +\*(TX's PRNG implementation addresses "problem 1" first problem by padding the +unseeded portions of the state space with random values (from a static table +that doesn't change). For instance, if the integer 1 is used to seed the space, +then one 32 bit word of the space is set to the value 1. The remaining 15 are +populated from the random table. This helps to ensure that a good PRNG sequence +is obtained immediately. However, it doesn't address "problem 2": that +similar seed values generate similar sequences, when the warm-up period is +small. For instance, if 65536 different random state objects are created, from +each of the 16-bit seeds in the range [0, 65536), and then a random 16-bit +value is extracted from each state, only 1024 unique values result. + .coNP Function @ make-random-state .synb .mets (make-random-state << [ seed <> [ warmup-period ]) @@ -41662,6 +41678,15 @@ of these version values, the described behaviors are provided if is given an argument which is equal or lower. For instance .code "-C 103" selects the behaviors described below for version 105, but not those for 102. +.IP 139 +After \*(TX 139, changes were implemented in the area of pseudo-random +number generation. Compatibility with 139 brings back the previous +seeding algorithm used by +.codn make-random-state , +allowing the old pseudo-random sequences to be reproduced. This is only +the case if the default value of 8 is used for the +.meta warmup-period +argument of that function (which didn't exist in 139 or earlier versions). .IP 138 After \*(TX 138, the variable name lookup rules in the \*(TX pattern language changed for greater utility and consistency. Compatibility with 138 or later |