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$ position 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.

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 improvement

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}$.

Source code

It also computes the period. Use for values of $N$ smaller than 45.

$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";