[C++ Automata-based RNG] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
C++ Automata-based RNG
(Click here to view the original thread with full colors/images)
Posted by: Jonathan Wooldridge
Hi,
I have a C++ project going on that involves a random number generator, and I'm interested in implementing an automata-based RNG for it.
Project: C++ Hat random container
What I've got so far: Implementation of a NKS RNG
However, the diehard battery of tests give poor results on my implementation, which I suspect is entirely my fault. So maybe some bright eyes could help me understand and improve this implementation?
Orientation:
Using a 32-bit variable as the 'width' of the automata's world, and wrapping bits at the ends. (Currently, I think there's a bug in the wrap-around code).
In order to get neighbor bits, it's mechanically more convenient to create a left-shifted copy and a right-shifted copy of the whole bitstring. So there are three full bitstrings: left, center and right. Then I apply the generation rule:
next_bit_string = left XOR ( center OR right )
which provides the next iteration.
During one call to the rng, it cycles through 32 iterations, and at each step it records the center bit into a result, and then returns the result.
So: Am I missing something, or should this be done differently?
typical debugging output:
-- ---------------X----------------
00 --------------+X+---------------
01 -------------+-O++--------------
02 ------------+++X-++-------------
03 -----------+---X--++------------
04 ----------+++-+X++-++-----------
05 ---------+--+--O-+--++----------
06 --------++++++-O++++-++---------
07 -------+-----++X---+--++--------
08 ------+++---+--X+-++++-++-------
09 -----+--++-++++O+----+--++------
10 ----++++-+----+O++--++++-++-----
11 ---+---+-++--++O-+++---+--++----
12 --+++-++--+++-+X+--++-++++-++---
13 -+--+--+++--+--O+++-+----+--++--
14 +++++++--+++++-X--+-++--++++-++-
15 ------+++----+-X+++--+++---+--+-
16 -----+--++--++-O--+++--++-++++++
17 +---++++-+++-++O-+--+++-+------+
18 ++-+---+---+--+X++++--+-++----+-
19 -+-++-+++-++++-O---++++--++--++-
20 ++--+---+----++O--+---+++-+++-++
21 -+++++-+++--+-+X-+++-+--+---+---
22 +----+---++++--X---+-+++++-+++--
23 ++--+++-+---+++X+-++-----+---+++
24 -+++--+-++-+---O+--++---+++-+---
25 +--++++--+-++--X+++-++-+--+-++--
26 +++---++++--+++O--+--+-++++--+++
27 --++-+---+++--+X-+++++----+++---
28 -+-+-++-+--+++-X-----++--+--++--
29 ++-+--+-+++--+-X+---+-++++++-++-
30 -+-++++---++++-O++-++------+--+-
31 ++----++-+---++X-+--++----++++++
At line #14, the pattern strikes the 'edges' (wraps around the cylender) and an interference pattern can then return inward. The 'lightcone' of effect impacts the center column on the final two lines.
Posted by: Jonathan Wooldridge
Here's a copy of diehard battery test results; my guess is that it may also have to do with having a bit-width of 32 bits, and the pattern reflecting across itself.
Posted by: Jonathan Wooldridge
Out of curiosity, I restructured the code to use a 64-bit wide world.
-- -------------------------------X-------------------------------- (seed)
00 ------------------------------+X+-------------------------------
01 -----------------------------+-O++------------------------------
02 ----------------------------+++X-++-----------------------------
03 ---------------------------+---X--++----------------------------
04 --------------------------+++-+X++-++---------------------------
05 -------------------------+--+--O-+--++--------------------------
06 ------------------------++++++-O++++-++-------------------------
07 -----------------------+-----++X---+--++------------------------
08 ----------------------+++---+--X+-++++-++-----------------------
09 ---------------------+--++-++++O+----+--++----------------------
10 --------------------++++-+----+O++--++++-++---------------------
11 -------------------+---+-++--++O-+++---+--++--------------------
12 ------------------+++-++--+++-+X+--++-++++-++-------------------
13 -----------------+--+--+++--+--O+++-+----+--++------------------
14 ----------------+++++++--+++++-X--+-++--++++-++-----------------
15 ---------------+------+++----+-X+++--+++---+--++----------------
16 --------------+++----+--++--++-O--+++--++-++++-++---------------
17 -------------+--++--++++-+++-++O-+--+++-+----+--++--------------
18 ------------++++-+++---+---+--+X++++--+-++--++++-++-------------
19 -----------+---+---++-+++-++++-O---++++--+++---+--++------------
20 ----------+++-+++-+-+---+----++O--+---+++--++-++++-++-----------
21 ---------+--+---+-+-++-+++--+-+X-+++-+--+++-+----+--++----------
22 --------++++++-++-+--+---++++--X---+-+++--+-++--++++-++---------
23 -------+-----+--+-+++++-+---+++X+-++---++++--+++---+--++--------
24 ------+++---+++++-----+-++-+---O+--++-+---+++--++-++++-++-------
25 -----+--++-+----++---++--+-++--X+++-+-++-+--+++-+----+--++------
26 ----++++-+-++--+-++-+-++++--+++O--+-+--+-+++--+-++--++++-++-----
27 ---+---+-+--++++--+-+----+++--+X-++-++++---++++--+++---+--++----
28 --+++-++-+++---++++-++--+--+++-X--+----++-+---+++--++-++++-++---
29 -+--+--+---++-+---+--++++++--+-X++++--+-+-++-+--+++-+----+--++--
30 +++++++++-+-+-++-++++-----++++-O---++++-+--+-+++--+-++--++++-++-
31 --------+-+-+--+----++---+---++O--+---+-++++---++++--+++---+--+-
32 -------++-+-+++++--+-++-+++-+-+X-+++-++----++-+---+++--++-++++++
33 +-----+-+-+-----++++--+---+-+--X---+--++--+-+-++-+--+++-+------+
34 ++---++-+-++---+---+++++-++-+++X+-++++-++++-+--+-+++--+-++----+-
35 -++-+-+-+--++-+++-+----+--+----O+----+----+-++++---++++--++--++-
36 +-+-+-+-+++-+---+-++--++++++---X++--+++--++----++-+---+++-+++-++
37 +-+-+-+---+-++-++--+++-----++-+O-+++--+++-++--+-+-++-+--+---+---
38 +-+-+-++-++--+--+++--++---+-+-+X+--+++--+--++++-+--+-+++++-+++-+
39 +-+-+--+--++++++--+++-++-++-+--O+++--++++++---+-++++-----+---+--
40 +-+-++++++-----+++--+--+--+-++-X--+++-----++-++----++---+++-++++
41 +-+------++---+--++++++++++--+-X++--++---+-+--++--+-++-+--+-----
42 +-++----+-++-++++---------++++-O-+++-++-++-+++-++++--+-+++++---+
43 +--++--++--+----++-------+---++O+--+--+--+---+----++++-----++-+-
44 +++-+++-+++++--+-++-----+++-+-+O+++++++++++-+++--+---++---+-+-+-
45 --+---+-----++++--++---+--+-+-+O----------+---+++++-+-++-++-+-+-
46 -+++-+++---+---+++-++-+++++-+-+X---------+++-+----+-+--+--+-+-++
47 ---+---++-+++-+--+--+-----+-+--X+-------+--+-++--++-+++++++-+--+
48 +-+++-+-+---+-++++++++---++-+++O++-----+++++--+++-+-------+-++++
49 +---+-+-++-++--------++-+-+---+O-++---+----+++--+-++-----++-----
50 ++-++-+--+--++------+-+-+-++-++X+-++-+++--+--++++--++---+-++---+
51 -+--+-++++++-++----++-+-+--+---O+--+---++++++---+++-++-++--++-+-
52 +++++------+--++--+-+-+-+++++--X+++++-+-----++-+--+--+--+++-+-++
53 ----++----++++-++++-+-+-----+++O----+-++---+-+-+++++++++--+-+---
54 ---+-++--+---+----+-+-++---+--+X---++--++-++-+---------++++-++--
55 --++--+++++-+++--++-+--++-++++-X+-+-+++-+--+-++-------+---+--++-
56 -+-+++----+---+++-+-+++-+----+-O+-+---+-++++--++-----+++-++++-++
57 -+---++--+++-+--+-+---+-++--+++X+-++-++----+++-++---+--+----+--+
58 -++-+-+++--+-++++-++-++--+++---O+--+--++--+--+--++-++++++--+++++
59 --+-+---++++----+--+--+++--++--X++++++-+++++++++-+------+++----+
60 +++-++-+---++--+++++++--+++-+++O-----+---------+-++----+--++--++
61 --+--+-++-+-+++------+++--+---+X----+++-------++--++--++++-+++--
62 -+++++--+-+---++----+--+++++-+-X+--+--++-----+-+++-+++---+---++-
63 +----++++-++-+-++--++++----+-+-O++++++-++---++---+---++-+++-+-++
The results are similar to the 32-bit version.
What does the Mathematica CARule30 RNG do differently?
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings