## arithmetic/src/misc/stochastic/RandomWolframCA.m3

```MODULE RandomWolframCA;
```
Gnu CopyLefted.

Abstract: Pseudo-random number generator by Warren D. Smith.

```IMPORT RandomBasic, Word;
IMPORT RandomRep;

<* UNUSED *>
CONST
Module = "RandomWolframCA.";

CONST
wolfnum = 5;
MSbit   = Word.LeftShift(2_1, Word.Size - 1);

REVEAL
T = TPublic BRANDED OBJECT
wolfarr: ARRAY [0 .. wolfnum - 1] OF Word.T;  (* initialize with
random bits *)
OVERRIDES
init   := Init;
engine := Engine;
END;

PROCEDURE Init (SELF: T; initrng: RandomBasic.T; ): T =
VAR
BEGIN
FOR i := wolfnum - 1 TO 0 BY -1 DO
SELF.wolfarr[i] := initrng.generateWord();
END;
RETURN SELF;
END Init;
```
************************************************************ S.Wolfram: Advances Applied Math 7 (1986) 123- had proposed the following nonlinear `cellular automaton` random number generator: Consider a 1D circular array of bits B[0..modulus-1]. At the t-th time step, you update according to Bnew[i] = Bold[i-1] XOR ( Bold[i] OR Bold[i+1] ) where the subscripts have circular wraparound. (Somehow, I don't think a 1-line formula involving 3 bits published in 1986 is out of the public domain.) The time-series B form a random-appearing bit sequence, according to a large number of empirical tests by Wolfram. Unfortunately you only get 1 bit at a time. An equivalent formula in the bit-complement universe is Bnew[i] = Bold[i-1] XOR ( Bold[i] AND Bold[i+1] ) and this also suggests the new idea of replacing the bits B by nonnegative integers Y mod 2^wordsize and then Ynew[i] = Yold[i-1] + ( Yold[i] * Yold[i+1] ) would be the same as Wolfram on its LS bits, but will generate a full word at a time. ********************************************************

```PROCEDURE Engine (SELF: T; ): BOOLEAN =
VAR
origcarry, carry, borrow: BOOLEAN;
x, a, b                 : Word.T;
BEGIN
borrow := (Word.And(SELF.wolfarr, 2_1) # 0);
origcarry := (Word.And(SELF.wolfarr[LAST(SELF.wolfarr)], MSbit) # 0);
FOR i := LAST(SELF.wolfarr) TO FIRST(SELF.wolfarr) BY -1 DO
x := SELF.wolfarr[i];      (* old word *)
IF i > 0 THEN              (* get carry from word below [borrow is
from word above] *)
carry := (Word.And(SELF.wolfarr[i - 1], MSbit) # 0);
ELSE
carry := origcarry;
END;
a := Word.RightShift(x, 1);
a := Word.Or(a, Word.LeftShift(ORD(borrow), Word.Size - 1));
b := Word.LeftShift(x, 1);
b := Word.Or(b, ORD(carry));
(* CA update formula -> new word: *)
SELF.wolfarr[i] := Word.Xor(a, Word.Or(x, b));
(* get borrow from old word for next time: *)
borrow := (Word.And(x, 2_1) # 0);
END;
RETURN borrow;
END Engine;

BEGIN
END RandomWolframCA.
```
```

```