|
|
 |
| Re: Random number generation using a 256-state cellular automaton |
|
 |
|
 |
|
 |
|
 |
Author: Bob Jenkins Date: Jan 24, 2007 00:23
On Jan 15, 6:37 am, oblivi...@ yahoo.com wrote: > Hi everyone,
>
> I developed a 256-state cellular automaton that serves as a random
> number generator. It's more than three times faster than the GNU
> Scientific Library RNGs I tested (taus, gfsr4, mt19937, and ranlxd1)
> and scores very well on the Diehard tests.
>
> It's fast because the algorithm is basically an array lookup with
> pointer value updates.
>
> Alas, there is no proof about cycles or such, but the statistical
> results so far are very good. Enjoy.
>
> Code and results are here:
>
> http://home.southernct.edu/~pasqualonia1/ca/report.html
>
> Tony Pasqualoni
When I use a seed of 2, then for all i, result 2056*i+2055 has a low
byte value of 3. Since the distribution of the value 3 is otherwise
about uniform, 3 is overall much more likely than it ought to be (for
that seed). More generally,
if (cell_a == first_cell) {
*cell_a = rule[*cell_a];
implies the low byte of 2056*i+2055 will be walking through your rule[]
table. That always has a cycle length of 169, or 27, or 4 or 3 or 2 or
1, depending on your seed.
I liked your trick of having a 511-element rule[] table, with rule[a+b]
lookup, rather than the more traditional 256-element rule[] table with
rule[(a+b)&0xff] lookup. I had to stare at it awhile to figure out why
204 (which only appears once in rule[]) wasn't an unusually rare result.
|
|
|
|
|
|
|
|
