and*_*ora 8 random algorithm numerical-methods
我希望生成一个伪随机数/置换,它在一个范围内"占据"一个完整的周期或整个周期.通常,"线性同余发生器"(LCG)可用于生成此类序列,使用如下公式:
X = (a*Xs+c) Mod R
其中Xs是种子,X是结果,a和c是相对的素数常数,R是最大值(范围).
(通过完整周期/完整周期,我的意思是可以选择常数,使得任何X在一些随机/置换序列中仅出现一次,并且将在0到R-1或1到R的范围内).
LCG几乎满足了我的所有需求.我对LCG的问题是奇数/偶数结果的非随机性,即:对于种子Xn,结果X将交替奇数/偶数.
问题:
有没有人知道如何创造类似的东西,不会交替奇/偶？
我相信可以建立'复合LCG',但我没有细节.有人可以举一个这个CLCG的例子吗？
是否有替代公式可能符合上述细节和下面的约束？
约束:
计算不应该溢出并且有效/快速,即:没有大的指数或几十个乘法/除法.
序列不一定非常随机或安全 - 我不需要加密随机性(但如果可行则可以使用它),只需要"好"随机性或明显随机性,没有奇数/偶数序列.
任何想法都赞赏 - 提前感谢.
更新:理想情况下,Range变量可能不是2的精确幂,但在任何一种情况下都应该有效.
琐碎的解决方案.请用LCG R比你想的范围更大一些,两者的黄金a,并c在该范围内的某处随机的.如果它给出的数字大于您想要的数字,请再次迭代,直到您回到范围内.
数字输出将没有特别简单的模式mod 2,3,5等,直到任何素数小于你使用的素数.
如果你想要的范围很大,那么最接近的较大的素数只会是一个较小的量,所以你很少需要调用它两次.例如,如果您想要的范围是十亿,那么您可以使用1000000007作为素数,并且您需要跳过少于0.000001%的额外数字.
我通过访问http://primes.utm.edu/curios/includes/primetest.php并输入数字直到我得到一个素数来找到这个素数.我有点幸运.n结束的几率1, 3, 7, 9是大约2.5/log(n)是十亿,大约12%,所以我有点幸运在4次尝试后找到这个数字.但不是那么幸运 - 我发现它有3次尝试,平均而言我应该需要8次.
编辑:这个随机数发生器可以有一个更短的周期.请参阅@dzugaru的说明.
如果奇数/偶数交替是您唯一的问题，请保持状态更改计算不变。在使用每个输出之前，您可以将低位移出或交换位。
编辑：
使用位交换（固定模式）变体，您将继续生成整个周期。
初始LCG的伪代码：
function rand
state := update(state)
return state
包括交换的 LCG 伪代码：
function rand2
state := update(state) -- unchanged state computation
return swapped(state) -- output swapped state