编写一个36位随机数发生器

Question

我正在一个具有特色的环境中编写应用程序

• 36位一的补码整数
• 算术限于+,-,*,/和余
• 没有像AND或的位操作OR.但由于一个人的补充,XOR相当于减法和NOT否定.
• 数字溢出是致命的,因此不能用于静默截断
• 是的,有条件:IF/THEN/ELSEIF/ELSE/IF.

理想情况下,我想要35或36位随机整数,但25位也足够了.

如果基于足够大的数字,我的线性同余生成器的天真实现会遇到溢出,并且当我使用较小的数字时,只生成少量的位.

因此,我正在寻找一组数字a,c,m,它们将产生约束中的最大位数,或者合理地调整LCG以组合2个或更多数字.

作为一个起点,这是我到目前为止所使用的:

*DEFINE NextRandom . min,max resultVar
* . This is a very shitty RNG. The numbers were never checked
* . for suitability for a long-period linear congruential generator.
* . But it yields numbers that look vaguely random.
*CLEAR rq
*CLEAR rr
*SET RandZ = RandZ * 169687 + 347011      . RandZ is a global var.
*DIVIDE RandZ BY 131072 GIVING rq, RandZ  . Division yields a remainder
*DIVIDE RandZ BY 4 GIVING rq
*SET r0 = +[#,[#],1,1]                    . r0 = argument 'min'
*SET r9 = +[#,[#],1,2]                    . r9 = 'max'
*SET rd = r9 - r0 + 1
*DIVIDE rq BY rd GIVING rq, rr
*SET [#,[#],2,1] TO r0 + rr               . return in 'resultVar'
*ENDDEFINE

---

如果有人关心,脚本语言是UNISYS 2200大型机操作系统EXEC 8中的SSG(符号流生成器).

---

关键性:RNG工作的应用程序生成测试数据.它不加密国家机密或核导弹代码.所以我们谈的是"很高兴"和"尽力而为",而不是"关键任务".我对改进感到高兴,但我不是在寻找最终的解决方案.

Answer 1

有可能编写一个永远不会溢出的线性同余随机数发生器,正如Stephen K. Park和Keith W. Miller 在他们的论文中证明的随机数发生器:好的很难找到:

function  Random  :  real; 
                  (*  Integer  Version  2  *) 
const 
  a  =  16807; 
  m  =  2147483647; 
  q  =  127773;  (*  m  div  a  *) 
  r  =  2836;  (*  m  mod  a  *) 
var 
  lo,  hi,  test  :  integer; 
begin 
  hi  :=  seed  div  q; 
  lo  :=  seed  mod  q; 
  test  :=  a  *  lo  -  r  *  hi; 
  if  test  >  0  then 
    seed  :=  test 
  else 
    seed  :=  test  +  m; 
  Random  :=  seed  /  m 
end;

这里m是2 ^ 31-1,但你可以改变它以产生36位数字.诀窍是将种子分成hi和lo部分,并通过对部分求和来生成最终的随机数.

如果您不喜欢,我的博客上有很多随机数生成器.也许其中一个会做你想做的事.