Re: Random number generation using a 256-state cellular automaton



On 23 Gen, 00:59, Michael Olea <o...@xxxxxxxxxxxxx> wrote:

A picture:

{ Table 1 }
|x_0|x_1|...|x_255=y_0|y_1|...|Y_255|
{ Table 2 }

Actually it's:
|x_0|x_1|...|x_254|x_255|x_0|x_1|...|x_254|

I misunderstood your remark about 256-periodic sequence to mean that each
table is a cyclic permutation of length 256. That is not the case. The
permutation in the lower half of the rule array has 11 non-trivial disjoint
cycles (cycles of length > 1) and 37 elements stabilized (cycles of length
1, which map x to x - for exanple, rule[3] = 3). The permutation in the
upper half also has 11 disjoint cycles, but 0 elements stabilized. The
distribution of cycle lengths is:

Table 1
Len Count
169 1
27 1
4 1
3 3
2 5
1 37

Table 2
Len Count
82 1
76 1
26 1
23 1
21 1
9 1
7 1
5 1
3 1
2 2

I don't know if this cyclic structure is really relevant to the
algorithm, since the value of a cell is added to the value of the
adjacent cell at each iteration.

I didn't find any other regularity for now, but i tried the algorithm
with other tables generated in accordance to the property stated above.
With the "identity modulo 256" table, the algorithm fails miserably the
Diehard tests, but with tables generated (pseudo)randomly it has
performances comparable with the original (slightly better or worse
depending on the particular table).

That's interesting. There are 256! * 255! rule tables in this space. I
wonder what the fitness landscape looks like. If rule tables generated at
random are comparable to Tony's, then I guess it must be fairly "flat" - if
your random tables were drawn from a uniform distribution over the space...

I drawn tables from a space of 256! tables, since I used the constraint
that the second half of the table is a copy of the first stripped of
its last element.
I used extraction without replacement to fill the first part of the
table. I think this gives uniform probability over the permutation
space (doesn't it?)

.