While investigating non-periodic RNG's (random number generators) for irrational numbers, I came up with a version that actually produces pseudo-random words consisting of $N$ bits, where $N$ is typically a large prime number. Here I explain my RNG. My question is whether it suffers from the same problems as [Xorshift][1] RNG's or some other problems. As a starter, the version corresponding to $N=32$ is terrible: its period is $24$. But $N=31$ yields a good generator with a long period and nice statistical properties. In its basic version, it is defined as follows.
Start with a seed $S$. The first random word $B_0$ is $S$. In my case, I picked up the first $N$ binary digits of $\sqrt{2}/2$ for the seed.The $k$-th bit of $B_n$ is denoted as $B_n(k)$. Then $B_{n+1}$ is obtained recursively as follows.
- **Shifting step**: Create the word $C_{n}$ by shifting the bits of $B_{n}$
by $L$ positions as follows: the $k$-th bit of $C_n$ is equal to $C_n(k)=B_n(\bmod(k+L,N))$ for $k=0,\cdots, N-1$.
- **Scrambling step**: $B_{n+1}(k)=\bmod(B_{n}(N-k-1)+C_{n}(k),2)$ for $k=0,\cdots, N-1$. In other words, $B_{n+1}(k)=\mbox{ XOR}(B_{n}(N-k-1),C_{n}(k))$. Thus the analogy with Xorshift generators.
$L=2$ seems to work best in most cases. For $L=2$ and $N=7, 11$ or $17$, the period is $2^{N-3}-1$. More generally, if $N$ is prime, the period is of the order $2^N$. Of course, there is no way the period could be higher than $2^N$. So prime values of $N$ produce the best generators, though this might not be true for all primes.
Also, the real number $X_n\in [0,1]$ is defined as follows:
$$X_n=\sum_{k=1}^{N} \frac{B_{n}(k-1)}{2^k}.$$
There is a one-to-one mapping between $B_n$ and $X_n$. I studied the patterns in the distribution of successive values of $X_n$ and haven't found any. For instance, unlike other RNG's (see [here][2] and follow-up discussion [here][3]), the triplets $(X_n,X_{n+1},X_{n+2})$ do not appear to lie in a small number of parallel planes. Successive values of $X_n$ are asymptotically un-correlated. For modern tests (George Marsaglia, 2020) to assess the quality of a RNG, see [here][4] and [here][5].
The underlying idea in the design of my generator is this: take a seed consisting of a large number of random bits, such as a the first $N$ binary digits of a [normal number][6] in base $2$. Then if you reverse these bits (the binary digits), the new number is a sequence of bits just as random as the previous one, and uncorrelated to the previous number.
**Possible improvements**
Consider a $q$-order recursion $B_{n}=f(B_{n-1},\cdots,B_{n-q})$ instead of a first-order one as here. Then the period can be of the order $2^{Nq}$. Such an example for a Xorshift generator is provided [here][7] by G. Marsaglia, with $q=4$. It uses four seeds. In our case, if we were to use $q$ seeds, you can pick up $q$ irrational numbers that are linearly independent over the set of rational numbers. Their digits sequences are independent from each other (see section 1.3 [in this article][8] for a proof). An example (with $q=4$) is the first $N$ binary digits of the following numbers: $\log 2, \frac{\pi}{4}, \frac{\sqrt{2}}{2}$ and $\exp(-\frac{3}{5})$.
Of course, instead of choosing $\sqrt{2}/2$, one might choose an irrational number impossible to guess, for instance
$$\alpha=\zeta(\sqrt{31}\log 5)\cdot\Gamma(e^{73 \sin 7})+\psi_2\Big(5e^{-11\cos 19}\log(53\pi+\sin 101)\Big)$$
Further improvement is obtained by using $N$ digits of $\alpha$ or $\sqrt{2}/2$ starting at position $M$ in their binary expansion, with $M$ very large and kept secret, rather than $M=0$ as in the code below. If you work with $q$ seeds, choose a different $M$ for each seed.
**Source code**
It also computes the period. If the period is larger than Niter (in the code) it will return $-1$ for the period: you need to increase Niter accordingly. Use for values of $N$ smaller than 45; to eliminate this problem, get the digits of the seed from a table or use a tool such as [this one][9] to get millions of digits for the seed.
#!/usr/bin/perl
$N=31;
$L=2;
$period=-1;
$Niter=50000;
%hash=();
$seed=sqrt(2)/2;
open(OUT,">randx.txt");
print OUT "0\tB";
$x=0;
$word="B";
$s=$seed;
for ($k=0; $k<$N; $k++) {
$a[$k]=int(2*$s); # k-th digit of seed
$s=2*$s-int(2*$s);
$b[$k]=$a[$k];
$x+=$b[$k]/(2**($k+1));
$word=$word."$b[$k]";
$hash{$word}=0;
print OUT "$b[$k]";
}
print OUT "\t$x\n";
for ($iter=1; $iter<$Niter; $iter++) {
print OUT "$iter\tB";
$x=0;
for ($k=0; $k<$N; $k++) {
$c[$k]=$b[($k+$L)%$N];
}
$word2="B";
$nzero=0;
for ($k=0; $k<$N; $k++) {
$b[$k]=($c[$k]+$b[$N-$k-1])%2;
$word2=$word2."$b[$k]";
$x+=$b[$k]/(2**($k+1));
print OUT "$b[$k]";
}
print OUT "\t$x\n";
if ($period==-1) {
if ($hash{$word2} eq "") {
$hash{$word2}=$iter;
} else {
$period=$iter-$hash{$word2};
}
}
}
close(OUT);
print "$N $L $period\n";
**Note**
Obviously, one flaw of all RNG's with $q=1$ (first-order recurrence) is that you never see twice the same word within any period cycle. In true randomness, repetition occurs without causing the cycle to repeat itself entirely. As an example, if you pick up 10 integers randomly between $0$ and $3$, some number MUST appear at least twice.
[1]: https://en.wikipedia.org/wiki/Xorshift
[2]: https://mathoverflow.net/questions/372103/recursive-random-number-generator-based-on-irrational-numbers
[3]: https://mathoverflow.net/questions/372712/hybrid-numeration-system-on-0-12/372738
[4]: https://www.researchgate.net/publication/5142801_Some_Difficult-to-Pass_Tests_of_Randomness
[5]: http://interstat.statjournals.net/YEAR/2006/articles/0601001.pdf
[6]: https://en.wikipedia.org/wiki/Normal_number
[7]: https://www.researchgate.net/publication/5142825_Xorshift_RNGs
[8]: https://www.datasciencecentral.com/profiles/blogs/state-of-the-art-statistical-science-to-address-famous-number-the
[9]: https://sagecell.sagemath.org/?z=eJzz0yguLCrRMNLUKShKTbY1NAACTb3ikiKNpMTiVFsjTQCp3gnT&lang=sage