Skip to main content
Added note at the bottom
Source Link

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.

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.

edited body
Source Link

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, canyou 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})$.

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, can 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})$.

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

Added new material to sections "possible improvements" and "source code"
Source Link

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.

Possible improvementimprovements

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, can 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.

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 4545; 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.

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.

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

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

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.

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, can 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.

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.

I added #!/usr/bin/perl at the top in the source code as requested in the answer to my question. Now you know it's written in Perl.
Source Link
Loading
Added reference on modern tests of ransomness
Source Link
Loading
Error in formula for $X_n$ fixed.
Source Link
Loading
Source Link
Loading