Elementary cellular automaton/Random number generator

Elementary cellular automaton/Random number generator is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

EDIT: The requirements of this task have recently been slightly modified. Please update your solution if necessary.

Rule 30 is considered to be chaotic enough to generate good pseudo-random numbers. As a matter of fact, rule 30 is used by the Mathematica software for its default random number generator.

Steven Wolfram's recommendation for random number generation from rule 30 consists in extracting successive bits in a fixed position in the array of cells, as the automaton changes state.

The purpose of this task is to demonstrate this. With the code written in the parent task, which you don't need to re-write here, show the ten first bytes that emerge from this recommendation. To be precise, you will start with a state of all cells but one equal to zero, and you'll follow the evolution of the particular cell whose state was initially one. Then you'll regroup those bits by packets of eight, reconstituting bytes with the first bit being the most significant.

The number of cells should be a finite, reasonably large number of your choice. The cells must warp on boundaries: this means that the right-most cell is considered as the left neighbor of the left-most cell, and reciprocally.

For extra-credits, you will make this algorithm run as fast as possible in your language, for instance with an extensive use of bitwise logic.

Reference

• Cellular automata: Is Rule 30 random? (PDF).

C

64-bits array size, cyclic borders. <lang c>#include <stdio.h>

1. include <limits.h>

typedef unsigned long long ull;

1. define N (sizeof(ull) * CHAR_BIT)
2. define B(x) (1ULL << (x))

void evolve(ull state, int rule) { int i, p, q, b;

for (p = 0; p < 10; p++) { for (b = 0, q = 8; q--; ) { ull st = state; b |= (st&1) << q;

for (state = i = 0; i < N; i++) if (rule & B(7 & (st>>(i-1) | st<<(N+1-i)))) state |= B(i); } printf(" %d", b); } putchar('\n'); return; }

int main(void) { evolve(1, 30); return 0; }</lang>

Output:

 220 197 147 174 117 97 149 171 100 151

Perl

Translation of: Perl 6

<lang perl>my $a = Automaton->new(30, 1, map 0, 1 .. 100);

for my $n (1 .. 10) {

   my $sum = 0;
   for my $b (1 .. 8) {

$sum = $sum * 2 + $a->{cells}[0]; $a->next;

   }
   print $sum, $n == 10 ? "\n" : " ";

}</lang>

Output:

220 197 147 174 117 97 149 171 240 241

Perl 6

<lang perl6>my Automaton $a .= new: :rule(30), :cells( 1, 0 xx 100 );

say :2[$a++.cells[0] xx 8] xx 10;</lang>

Output:

220 197 147 174 117 97 149 171 240 241

Python

Python: With zero padded ends

<lang python>from elementary_cellular_automaton import eca, eca_wrap

def rule30bytes(lencells=100):

   cells = '1' + '0' * (lencells - 1)
   gen = eca(cells, 30)
   while True:
       yield int(.join(next(gen)[0] for i in range(8)), 2)

if __name__ == '__main__':

   print([b for i,b in zip(range(10), rule30bytes())])</lang>

Output:

[255, 255, 255, 255, 255, 255, 255, 255, 255, 255]

!

Python: With wrapping of end cells

<lang python>def rule30bytes(lencells=100):

   cells = '1' + '0' * (lencells - 1)
   gen = eca_wrap(cells, 30)
   while True:
       yield int(.join(next(gen)[0] for i in range(8)), 2))</lang>

Output:

[220, 197, 147, 174, 117, 97, 149, 171, 240, 241]

Tcl

Works with: Tcl version 8.6

<lang tcl>oo::class create RandomGenerator {

   superclass ElementaryAutomaton
   variable s
   constructor {stateLength} {

next 30 set s [split 1[string repeat 0 $stateLength] ""]

   }

   method rand {} {

set bits {} while {[llength $bits] < 8} { lappend bits [lindex $s 0] set s [my evolve $s] } return [scan [join $bits ""] %b]

   }

}</lang> Demonstrating: <lang tcl>set rng [RandomGenerator new 31] for {set r {}} {[llength $r]<10} {} {

   lappend r [$rng rand]

} puts [join $r ,]</lang>

Output:

220,197,147,174,241,126,135,130,143,234

Note that as the number of state bits is increased (the parameter to the constructor), the sequence tends to a limit of $220,$ $197,$ $147,$ $174,$ $117,$ $97,$ $149,$ $171,$ $240,$ $241,$ $\ldots$ and that deviations from this are due to interactions between the state modification “wavefront” as the automaton wraps round.