生成全周期/全周期随机数或排列，类似于LCG，但没有奇/偶 [英] Generating Full Period/Full Cycle Random Numbers or Permutations Similar to LCG but without odd/even

问题描述

我希望生成伪随机数/排列，它们在一个范围内占据了整个周期或整个周期。通常，线性同余生成器（LCG）可以使用以下公式生成此类序列：

  X = （a * Xs + c）Mod R 
  

其中Xs是种子，X是结果，a C是相对质数常数，R是最大值（范围）。

（通过全周期/全周期，我的意思是可以选择常数，以便任何X在某些随机/置换序列中只会出现一次，并且会在0到R-1或1到R的范围内。）

LCG几乎可以满足我的所有需求。我对LCG的问题是奇数/偶数结果的非随机性，即：对于种子Xn，结果X将交替为奇数/偶数。

问题：

1. 有人知道如何创建
   类似于$ b的东西吗$ b替代的奇/偶？




2. 我相信可以构建复合LCG
   ，但是我没有
   细节。有人可以举这个CLCG的
   例子吗？




3. 是否存在替代公式，表明
   可能满足上述详细信息，而
   

约束：

4. 我想要一些基于简单的
   基于种子的公式的东西。即：要获得
   的下一个数字，我需要提供种子，而
   则要获得置换后的序列
   中的下一个随机数。具体来说，
   我不能使用预先计算的数组。
   （请参阅下一个要点）


5. 序列绝对必须是整个周期/整个周期


6. 范围R可以是几个百万美元
   甚至32bit / 4十亿。



7. 计算不应该出现溢出并且有效/快速，即：没有大的指数或数十个乘除/除法。




8. 序列不必是非常随机的或安全的-我不需要密码随机性（但可以使用它，如果可行的话），只需良好随机性或明显的随机性，没有奇数/偶数序列。

任何想法都值得赞赏-预先感谢。

更新：理想情况下，Range变量可能不是精确的2的幂，但是在两种情况下都应该起作用。

解决方案

乘积。用 R 作质数比想要的范围大一些的LCG，并且 a 和 c 在该范围内的某个随机位置。如果它提供的数字大于所需的数字，请再次进行迭代，直到返回范围为止。

数字输出不会包含特别简单的模式mod 2， 3、5，等等，直至小于您使用的素数的素数。

如果您要的范围较大，则最接近的较大素数只会小一些，因此您很少需要调用两次。例如，如果您希望的范围是十亿，则可以使用1000000007作为质数，并且您需要跳过少于0.000001％的时间的额外数字。

我通过访问 http://primes.utm.edu/curios/includes找到了素数/primetest.php 并输入数字，直到获得质数。我有点幸运。以 1、3、7、9 结尾的 n 是素数的几率约为 2.5 / log（n）大约是12％，因此我很幸运在尝试了4次后就找到了这个数字。但不是那么幸运-我在3次尝试中发现它，平均来说我应该需要8。

编辑：该随机数生成器可以具有周期较短。请参阅@dzugaru的注释。

I wish to generate psuedo-random numbers/permutations that 'occupy' a full period or full cycle within a range. Usually an 'Linear Congruential Generator' (LCG) can be used to generate such sequences, using a formula such as:

X = (a*Xs+c) Mod R

Where Xs is the seed, X is the result, a and c are relatively prime constants and R is the maximum (range).

(By full period/full cycle, I mean that the constants can be chosen so that any X will occur only once in some random/permuted sequence and will be within the range of 0 to R-1 or 1 to R).

LCG almost meets all of my needs. The problem I have with LCG is the non-randomness of the odd/even result, ie: for a seed Xn, the result X will alternate odd/even.

Questions:

1. Does anybody know how to create something similar that will not alternate odd/even?

2. I believe that a 'Compound LCG' could be built, but I don't have details. Can somebody give an example of this CLCG?

3. Are there alternative formulas that might meet the details above and constraints below?

Constraints:

4. I want something based on a simple seed-based formula. ie: to get the next number, I provide the seed and get the next 'random number' in the permuted sequence. Specifically, I cannot use pre-calculated arrays. (See next points)
5. The sequence absolutely has to be 'full period/full cycle'
6. The range R could be several million or even 32bit/4 billion.

7. The calculation should not suffer overflow and be efficient/fast, ie: no large exponents or dozens of multiplies/divides.

8. Sequence does not have to be terribly random or secure - I do not need cryptographic randomness (but can use it if viable), just 'good' randomness or apparent randomness, without odd/even sequences.

Any thoughts appreciated - thanks in advance.

UPDATE: Ideally the Range variable may not be an exact power of two, but should work in either case.

解决方案

Trivial solution. Make a LCG with R a prime somewhat larger than the range you want, and both a and c somewhere random in that range. If it gives you a number that is larger than you want, iterate again until you are back in range.

The numbers output will not have a particularly simple pattern mod 2, 3, 5, etc up to any prime less than the prime you use.

If the range you want is large then the nearest larger prime will only be a small amount larger, so you'll very rarely need to call it twice. For example if your desired range is a billion, you can use 1000000007 as your prime, and you'll need to skip an extra number less than 0.000001% of the time.

I found this prime by going to http://primes.utm.edu/curios/includes/primetest.php and putting in numbers until I got a prime. I was a little lucky. The odds that n ending in 1, 3, 7, 9 are prime are approximately 2.5/log(n) which out at a billion are about 12%, so I was somewhat lucky to find this number after only 4 tries. But not that lucky - I found it in 3 tries and on average I should have needed 8.

EDIT: This random number generator can have a shorter cycle. See the note by @dzugaru.

这篇关于生成全周期/全周期随机数或排列，类似于LCG，但没有奇/偶的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！