Registered: Oct 2007
Posts: 4

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.

Last edited by Jonathan Wooldridge on 10-07-2007 at 09:16 PM

Report this post to a moderator | IP: Logged

Registered: Oct 2007
Posts: 4

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.

Attachment: analysis.txt
This has been downloaded 1006 time(s).

Last edited by Jonathan Wooldridge on 10-07-2007 at 08:36 AM

Report this post to a moderator | IP: Logged

Registered: Oct 2007
Posts: 4

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?

Attachment: analysis64.txt
This has been downloaded 1038 time(s).

Last edited by Jonathan Wooldridge on 10-07-2007 at 10:40 PM

Report this post to a moderator | IP: Logged