wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Applied NKS > C++ Automata-based RNG
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Jonathan Wooldridge


Registered: Oct 2007
Posts: 4

C++ Automata-based RNG

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

Old Post 10-06-2007 07:01 AM
Jonathan Wooldridge is offline Click Here to See the Profile for Jonathan Wooldridge Visit Jonathan Wooldridge's homepage! Edit/Delete Message Reply w/Quote
Jonathan Wooldridge


Registered: Oct 2007
Posts: 4

Analysis

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 1201 time(s).

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

Report this post to a moderator | IP: Logged

Old Post 10-06-2007 11:45 AM
Jonathan Wooldridge is offline Click Here to See the Profile for Jonathan Wooldridge Visit Jonathan Wooldridge's homepage! Edit/Delete Message Reply w/Quote
Jonathan Wooldridge


Registered: Oct 2007
Posts: 4

64-bit test

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 1227 time(s).

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

Report this post to a moderator | IP: Logged

Old Post 10-07-2007 10:30 PM
Jonathan Wooldridge is offline Click Here to See the Profile for Jonathan Wooldridge Visit Jonathan Wooldridge's homepage! Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives