# Question about a new pseudo-random number generator

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 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 and follow-up discussion here), 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 and here.

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 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 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 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 to get millions of digits for the seed.

#!/usr/bin/perl
$N=31; $$L=2;$$period=-1;$Niter=50000;

%hash=();