Cu convenția din implementare de referință, recurența este
$$u_{j+1}:=c\oplus(u_j\lll1)\oplus(u_j\vee(u_j\ggg1))$$
Unde $c$ este $n$-bit constant cu toți biții la $0$ cu excepția celui din dreapta (altfel spus $c=0^{n-1}\mathbin\|1$ ), $\oplus$ este XOR pe biți, $\vee$ este pe biți SAU, $\lll$ și $\ggg$ sunt rotații la stânga și la dreapta ale $n$-bit bistring înaintea operatorului cu numărul de biți de după.
Dacă inversăm direcția deplasărilor, aceasta oglindește pur și simplu maparea de biți (circulară), deci nu schimbă structura ciclului.
„Regula 30 cu comutare de biți” are durata minimă a ciclului de? ${\cal O}(2^n)$ Unde $n$ este lungimea vectorilor de biți?
Nu, deoarece pentru impar $n$ există un ciclu minim de lungime unu. Acest punct fix are o expresie binară o alternanță de $\frac{n+1}2\ 1$ și $\frac{n-1}2\ 0$ (în hexadecimal: 55â¦55 pentru $n\bmod 4=3$ sau 15â¦55 pentru $n\bmod 4=1$). În cele ce urmează ne limităm astfel la par $n$.
Explorând mic $n$ nu prezintă nicio dovadă în legătură cu afirmația: lungimea minimă a ciclului este adesea $3$, și nu pare să explodeze vertiginos.
n lungime început
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
Pentru o funcție aleatorie, dimensiunea așteptată a ciclului pornind de la un punct aleator este aproape de $\sqrt{\pi2^n/8}=\mathcal O(2^{n/2})$; vezi Flajolet&Odlyzko's Statistici de cartografiere aleatoare. Cel mai mic ciclu este de obicei mult mai mic (deși nu știu distribuția așteptată). Astfel, lungimea ciclului revendicată ar fi oarecum o surpriză.
Pe de altă parte, funcția are difuzie foarte lentă, deci este foarte departe de o funcție aleatorie.
Iată un grafic pentru $n=14$.
