Join Log in
Score:0
Tom avatar Crypto

Adding Weyl sequence to random mapping - expected cycle size

tf flag
Tom

In order to improve the quality of random generators, Weyl sequences have been added to the Middle Square (Widynski) and Xorshift (Marsaglia) generators:

https://arxiv.org/abs/1704.00358

https://www.jstatsoft.org/article/view/v008i14

As I understand, it was also about extending generator cycles, especially when it comes to Middle Square, which works like random mapping.

I also have a generator that works like random mapping. The cycle lengths of an n-bit generator are close to $\sqrt{\pi \frac{2^{n}}{8}}$ (although usually slightly shorter, probably because of imperfections of the generator). Now I'm adding Weyl sequence to the output, which became new input to the generator. And now generator is reaching maximum cycle length for different keys (it is keyed) and seeds.

Is there any theory behind that? My guess is that you can prove that if we do something like this with random mapping, you will achieve the maximum cycle lengths since these two authors did it. On the other hand, it seems difficult to prove to me.

30
0 + 0
kodlu avatar
sa flag
kodlu
did they actually prove it in their paper? note that a mapping modulo a composite $n$ can have a preperiod, i.e., a rho type iteration map.
0
Reply
Tom avatar
tf flag
Tom
@kodlu If I understand correctly Widynski's work, he only proved it for his Middle Square. Marsaglia made no mention about proof. So I'm not sure if such evidence exists for the (not perfect) random mapping. When it comes to preperiods, not only do I observe them, but numbers can appear several times before they fall into the cycle. Let's consider 10-bit generator. Number 311 can may appear after 433, 122, 479 steps and then go into cycle, but not always trivial. It can be reached after 111,607,417,111,607,417,... steps (but all sequence repeats after 1024 steps).
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.