Score:1

Minimum cycle length for Rule 30 automaton with bit-toggle

br flag

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?

poncho avatar
my flag
For $n=32$, I found a cycle of length 6923; I do not know if it is the smallest possible...
Dominic van der Zypen avatar
br flag
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](https://en.wikipedia.org/wiki/Rule_30) 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.
Dominic van der Zypen avatar
br flag
Thanks @poncho - I suppose that makes smallest cycles too small...
ThomasM avatar
sk flag
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$$
Dominic van der Zypen avatar
br flag
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](https://github.com/dominiczypen/Bit_inverse_feedback_shift_register/blob/main/bfsr.c) is a simple implementation. Indeed the periods are quite long, possibly ${\cal O}(2^n)$.
Score:1
ng flag

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

poncho avatar
my flag
"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.
Dominic van der Zypen avatar
br flag
Beautiful answer, thanks for your effort, fgrieu!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.