11

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

  • 36 位补码整数
  • 算术限于+, -, *,/和余数
  • 没有类似ANDor的位操作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

万一有人关心，脚本语言是名为 EXEC 8 的 UNISYS 2200 大型机操作系统中的 SSG（符号流生成器）。

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

4

2 回答 2

6

可以编写一个永远不会溢出的线性同余随机数生成器，正如 Stephen K. Park 和 Keith W. Miller在他们的论文Random Number Generators: Good Ones Are Hard To Find中所展示的：

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部分，最终的随机数是通过对这些部分求和来生成的。

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

于 2013-02-14T14:55:03.040 回答
1

只是一个简单的想法，我不知道这是否真的是最好的：你可以在 12 位上使用递归 3 个 LCG

x_i(n) = a x_i(n-1) + p_i (mod 2^{12})

有不同的素数 p_i。如果 a 不是太大（比如 12 位），它永远不会溢出。然后，使用 3 个 12 位随机数，可以生成一个 36 位随机整数：

z(n) = x_0(n) + 2^{12} x_1(n) + 2^{24} x_2(n)

请注意，如果 p_i 是素数且相对较大，则 3 个随机生成器应该是相当独立的，因此该策略应该是可以的。

难的是有一个好的选择。

无论如何，在使用它之前，我想它会更好地进行一些测试。

于 2013-02-14T14:22:35.307 回答