0
$\begingroup$

This question is a kinda spin off from Why do we not combine random number generators?

If for example we had N identical type random number generators, with N different seeds, what would the period be if their outputs were xored together? Would it be period, N x period or period (power N)?

So a numerical example would be:

2 linear feedback shift registers of 10 bits.

1 LFSR's period = 1023.

2 xored LFSRs' period = 1023, 2046 or 1046529?

(I have a sense that it's period but I can't overcome that fact that the state size is so much bigger.)

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ The period is hardly worth worrying about in practice; it's not the hard part. It's super-easy to build generators with a large period. What's harder is to build a generator that produces high-quality random output (i.e., where the outputs can't be predicted from previous outputs). So, the answer to your question probably won't be of much help in understanding whether it's useful to xor generators or not. $\endgroup$ – D.W.♦ Jan 13 '17 at 1:30
  • $\begingroup$ The link to the prior question is broken. Would you like to fix that? $\endgroup$ – D.W.♦ Jan 13 '17 at 1:31
2
$\begingroup$

I will assume the N random generators have independent seeds and states. Suppose their periods are $t_1,\dots,t_N$. Then the period of their xor is a divisor of $\operatorname{lcm}(t_1,\dots,t_N)$. Typically, it will be exactly $\operatorname{lcm}(t_1,\dots,t_N)$, but I don't know whether that is guaranteed in all cases.

If all $N$ generators have the same period $t$, then the period of their xor is a divisor of $t$ (and thus cannot be any larger than $t$).

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Err, does gcd mean greatest common denominator? $\endgroup$ – Paul Uszak Jan 13 '17 at 1:40
  • $\begingroup$ @PaulUszak, greatest common divisor: en.wikipedia.org/wiki/Greatest_common_divisor $\endgroup$ – D.W.♦ Jan 13 '17 at 1:44
  • $\begingroup$ Shouldn't it be the LCM? For example, the XOR of $(01)^\omega$ and $(001)^\omega$ is $(011100)^\omega$. $\endgroup$ – Yuval Filmus Mar 14 '17 at 3:20
  • $\begingroup$ @YuvalFilmus, oops! Yes, thank you for the correction. $\endgroup$ – D.W.♦ Mar 14 '17 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.