Middle-Square Weyl Sequence RNG - initialization for independent streams

[osobliwy nick]

I'm trying to analyze Middle-Square Weyl Sequence RNG by Bernard Widynski:

https://arxiv.org/pdf/1704.00358.pdf

The generator is very simple:

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws32() {
x *= x; x += (w += s); return x = (x>>32) | (x<<32);
}

It is random mapping with Weyl sequence. How random mappings (without Weyl sequence) generators works? You can initialize it and fall straight into the cycle or usually you will fall into a path to the cycle. Generator will produce some numbers and then will fall into the cycle.

But what happens when we add a Weyl sequence? According to my knowledge and research on the subject, such generator always follows a certain path, until finally also falls into a cycle (there can be many cycles). The thing is that by using Weyl sequence, we make sure that it won't happen after fewer iterations than the Weyl sequence cycle length. So the path to reach the cycle is always at least so long as Weyl sequence.

But I ask myself if we can generate independent streams using different initializations but the same constat in Weyl sequence (for example s = 0xb5ad4eceda1ce2a9). x shoudn't be used to initalization, because of what Widynski noted:

"Only w and s may be used to create a distinct initialization. If x is used, there is some danger that overlapping data will be produced. For example, let’s say that one initialized the state vector as follows:

x = 0; w = 0; s = 0xb5ad4eceda1ce2a9;

for the first run and then set the state

x = 232; w =0; s = 0xb5ad4eceda1ce2a9;

for the next run. In this case, exactly the same data would be generated
even though the initial x values are different."

But can we use w? Author wrote:

"Also, w may be used but one must assure sufficient space in between the values so there is no overlap."

But can overlappings really occur there (if we would use properly at most only 2^32 numbers of the generator)? Let's consider initialization of generator A:

x = 0; w = 0; s = 0xb5ad4eceda1ce2a9;

Now let's use another generator B with initalization:

x = 0; w = n; s = 0xb5ad4eceda1ce2a9;

Where n is some non-zero number. Let's consider that B is returning the same output after some number of steps as A. To note overlappings both generators should giving now the same values. But this is seem to be impossible, because the states of generators are different, regardless of the fact that they returned the same values at once.

I see such a possibility only if function which we use would give exactly the same results in a row for different states. Since we don't know exactly math behind this process we can't rule it out. But chance that somehow values of (x>>32) | (x<<32) would be the same by large number of iterations for completely different states of the generator seem negligible. Although we can only estimate it assuming we are dealing with a random process and estimating it (probability that we just draw exactly the same middle bits in a row, feeding function by different states).

So is it possible that for some different initalizations x = 0; w = 0; s = 0xb5ad4eceda1ce2a9; and x = 0; w = n; s = 0xb5ad4eceda1ce2a9; after some steps generator B will start to produce exactly the same output as generator A? Like I wrote we should consider only 2^32 outputs, because after more steps they can of course fall into the same cycle. In my opinion it is not possible, so we could use w as a parameter for independent streams.

I tested few parameters of 32-bit version with 16-bit ouput and s = 2654435769:

uint32_t x = 0, w = 7, s = 2654435769;
uint16_t result;

x *= x;
x += (w += s);
x = (x >> 16) | (x << 16);
result = x;

And inteleaving the outputs of two generators with w=0 and w=1, w=7, w=8 and few other ones. It passes PractRand to 2^31 bytes, the same as generator without interleaving outputs. So it looks like there don't have to be "sufficient space in between" w parameters as author wrote.  Am I  misunderstand  something or am I missing something important?

[osobliwy nick]

PS It looks like Widynski assumed that there is a cycle of length 2^32 or 2^32*d in which there are numbers generated by any w and x = 0 and s = 0xb5ad4eceda1ce2a9. So if we increase w, we jump further in the cycle. This does not seem to be true (because first is path to reach the cycle). According to the theory of random mappings:

https://link.springer.com/chapter/10.1007/3-540-46885-4_34

path to reach the cycle which is (pi/8 * N)^0.5 (in average) and then cycle of lenght (pi/8 * N)^0.5 (in average). So in random mapping with Weyl sequence (mod 2^32) there will be path lengh to reach the cycle ((pi/8 * 2^32)^0.5) * 2^32 and the cycle of expected lenght ((pi/8 * 2^32)^0.5) * 2^32. But it seems to me that it is impossible to fall into the cycle faster than after 2^32 steps. Even if we are unlucky and ((pi/8 * 2^32)^0.5) = 1, then there will be still 2^32 steps to reach the cycle. So there can't be overlappings.

But I'm not exactly sure is this theory of combined weyl-random mappings is right. Maybe some numbers can fall into the cycle after less than 2^32 steps and we can be only sure, that they will not repeat after less than 2^32. But for sure weyl sequence combined with random mapping extends the length of the cycle, hence it seems to also extend the path to reach the cycle (and perhaps it can be proved that it cannot be shorter than 2^32).

[osobliwy nick]

Ok, I made a mistake. In case of  Middle-Square Weyl Sequence RNG this is not how it works. This is invertible random mapping with Weyl sequence. It means there is a path to reach the cycle and the cycle. But my experimental result show that cycle is always of the length 2^n for n-bit generator. For example in scaled down 16-bit version there is a cycle of lenght 2^16. And with different initalization of "w" we get different path leghts to reach the cycle (s is fixex and x is always equal to 0 at the beginning). It looks like path lenght can be every number from 0 to 2^16-1, so in average has a lenght 2^16/2. So Widyński wasn't wrong.

But why I was wrong? It looks like statistics which I mentioned are appropriate in case of so called non-invertible random mappings with Weyl sequence (then it looks like it really works like in my first post). But again, I confirmed it only by experimental results, I have no proof.