Với quy ước trong Thực hiện tham khảo, sự lặp lại là
$$u_{j+1}:=c\oplus(u_j\lll1)\oplus(u_j\vee(u_j\ggg1))$$
ở đâu $c$ là $n$-bit không đổi với tất cả các bit tại $0$ ngoại trừ ngoài cùng bên phải (nói cách khác $c=0^{n-1}\mathbin\|1$ ), $\oplus$ là XOR theo bit, $\vee$ theo chiều bit HOẶC, $\lll$ và $\ggg$ là phép quay trái và phải của $n$-bit bistring trước toán tử bằng số bit sau.
Nếu chúng ta hoàn nguyên hướng dịch chuyển, điều đó chỉ phản ánh ánh xạ bit (tròn), do đó không thay đổi cấu trúc chu trình.
"Quy tắc 30 với chuyển đổi bit" có độ dài chu kỳ tối thiểu là ${\cal O}(2^n)$ ở đâu $n$ là độ dài của các vectơ bit?
Không, vì lẻ $n$ có một chu kỳ tối thiểu có độ dài một. Điểm cố định đó có biểu thức nhị phân xen kẽ $\frac{n+1}2\ 1$ và $\frac{n-1}2\ 0$ (trong hệ thập lục phân: 55â¦55 vì $n\bmod 4=3$ hoặc 15â¦55 vì $n\bmod 4=1$). Do đó, trong phần sau đây, chúng tôi giới hạn ở mức thậm chí $n$.
khám phá nhỏ $n$ cho thấy không có bằng chứng đối với tuyên bố: độ dài chu kỳ tối thiểu thường là $3$, và dường như không tăng vọt.
n chiều dài bắt đầu
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
Đối với một chức năng ngẫu nhiên, kích thước dự kiến của chu kỳ bắt đầu từ một điểm ngẫu nhiên gần bằng $\sqrt{\pi2^n/8}=\mathcal O(2^{n/2})$; xem Flajolet&Odlyzko's Thống kê ánh xạ ngẫu nhiên. Chu kỳ nhỏ nhất thường nhỏ hơn nhiều (mặc dù tôi không biết phân phối dự kiến). Do đó, độ dài chu kỳ được tuyên bố sẽ hơi bất ngờ.
Mặt khác, hàm này có độ khuếch tán rất chậm, do đó khác xa với hàm ngẫu nhiên.
Đây là một biểu đồ cho $n=14$.
