1
$\begingroup$

A rule 30 cellular automaton produces chaotic output from a very simple rule and therefore can be used as a pseudo-random generator (but not a cryptographically secure one).

One of the problems is that there are "black holes", for instance the constant 0 bit-vector gets mapped to itself, and the constant 1 vector gets mapped to constant 0.

This can be mended using a simple toggle (via XOR) of bit 0 (the right-most bit); this is a simple implementation in C.

Question. Does "Rule 30 with bit toggle" have minimum cycle length of ${\cal O}(2^n)$ where $n$ is the length of the bit vectors?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ For $n=32$, I found a cycle of length 6923; I do not know if it is the smallest possible... $\endgroup$
    – poncho
    Commented Apr 14, 2022 at 14:32
  • $\begingroup$ Thanks for this concise way of describing it @fgrieu ! Just one little thing, I think one has to swap $\lll$ and $\ggg$, as the rule described in Wikipedia is "left_cell XOR (central_cell OR right_cell)", and you get the left cell "aligned above" the center (origin) cell via a right shift / rotation, if I am not mistaken, and vice versa. So maybe it is $$u_{n+1} := \big((u_n \ggg 1) \oplus (u_n \lor (u_n \lll 1))\big) \; \oplus c$$ - but I guess, for considerations of length of period, it doesn't make a difference. $\endgroup$
    – Dominic van der Zypen
    Commented Apr 14, 2022 at 14:33
  • $\begingroup$ Thanks @poncho - I suppose that makes smallest cycles too small... $\endgroup$
    – Dominic van der Zypen
    Commented Apr 14, 2022 at 14:35
  • 1
    $\begingroup$ Not an answer to the question, but you might ensure high cycle length by XORing with a counter:$$u_{j+1}= (u_j \ggg 1) \oplus (u_j \vee (u_j \lll 1)) \oplus j$$ $\endgroup$
    – ThomasM
    Commented Apr 18, 2022 at 13:29
  • $\begingroup$ Good point @ThomasM -> I have indeed tried a similar thing: at every step one bit gets inverted at a different position, very similar to what you propose! The formula for this would be $$u_{j+1} = u_j \oplus (1 \lll j).$$ This is a simple implementation. Indeed the periods are quite long, possibly ${\cal O}(2^n)$. $\endgroup$
    – Dominic van der Zypen
    Commented Apr 18, 2022 at 18:48

1 Answer 1

Reset to default
1
$\begingroup$

With the convention in the reference implementation, the recurrence is $$u_{j+1}:=c\oplus(u_j\lll1)\oplus(u_j\vee(u_j\ggg1))$$ where $c$ is the $n$-bit constant with all bits at $0$ except the rightmost (otherwise said $c=0^{n-1}\mathbin\|1$ ), $\oplus$ is bitwise XOR, $\vee$ is bitwise OR, $\lll$ and $\ggg$ are left and right rotations of the $n$-bit bistring before the operator by the number of bits after.

If we revert the direction of shifts, that merely mirrors the (circular) bit mapping, thus does not change the cycle structure.

Does "Rule 30 with bit toggle" have minimum cycle length of ${\cal O}(2^n)$ where $n$ is the length of the bit vectors?

No, since for odd $n$ there is a minimum cycle of length one. That fixed point has binary expression an alternation of $\frac{n+1}2\ 1$ and $\frac{n-1}2\ 0$ (in hex: 55…55 for $n\bmod 4=3$ or 15…55 for $n\bmod 4=1$). In the following we thus restrict to even $n$.

Exploring small $n$ shows no evidence towards the claim: the minimum cycle length is often $3$, and does not seem to skyrocket.

 n   length       start
 2     2            0x0
 4     5            0x1
 6     3           0x03
 8     6           0x14
10     3          0x07C
12     5          0x42F
14     7         0x035D
16    33         0x2D34
18     3        0x03E43
20    27        0x00A28
22     3       0x07C87C
24     4       0x102040
26    14      0x0ABB343
28     5      0x2D1E5A3
30     3     0x03E43E43
32     7     0x1B3AFA05
34     3    0x07C87C87C
36    13    0x0217F5A73

For a random function, the expected size of the cycle starting from a random point is close to $\sqrt{\pi2^n/8}=\mathcal O(2^{n/2})$; see Flajolet&Odlyzko's Random mapping statistics. The smallest cycle is typically much smaller (though I don't know the expected distribution). Thus the claimed cycle length would be somewhat a surprise.

On the other hand, the function has very slow diffusion, thus is very far from a random function.

Here is a graph for $n=14$. Graph for n=14

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ "Thus the claimed cycle length would be somewhat a surprise."; is that my finding a cycle of length 6923? Well, that's the smallest cycle I saw; I also saw cycles of lengths 166839, 223545, 423038 and 1143461. Remember, the $\mathcal{O}(2^{n/2})$ is for a cycle from a random point; the smallest cycle may be considerably smaller. $\endgroup$
    – poncho
    Commented Apr 14, 2022 at 20:05
  • $\begingroup$ Beautiful answer, thanks for your effort, fgrieu! $\endgroup$
    – Dominic van der Zypen
    Commented Apr 15, 2022 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.