编写一个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

---

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

---

关于重要性：这个随机数生成器应用程序产生测试数据，它不会加密国家机密或核导弹代码。因此，我们谈论的是“好有但不必须”和“尽力而为”，而不是“使命至上”。我很乐意进行改进，但并不寻求最终解决方案。

- Carl Smotricz

---

你有条件语句吗？ - Pubby

你可以通过运行现有的代码生成一个种子值来改进你现在所拥有的。 - Security Hound

@Pubby：是的，有IF/THEN/ELSE/ENDIF。我会更新我的问题以反映这一点，谢谢！ - Carl Smotricz

@Ramhound：我使用一个系统值来为RandZ种子赋值，该值给出了我的CPU运行时间。 - Carl Smotricz

如果您生成4个9位数，然后将它们组合起来(result = a1 * 2^0 + a2 * 2^9 + a3 * 2^18 + a3 * 2^27)会怎样呢？这些9位数应该由具有不同周期的LCGs生成。如果所有周期都是互质的且互质于4，则总周期应该相当大。请注意，这只是一个快速的hack，生成的随机数将远非完美并且具有重复的模式（通过构造）。但根据您的需求，它可能足够，并且速度应该相当快。 - Carsten

@Carsten：你和Dr_Sam有相同的想法。请看一下我对他的评论！ - Carl Smotricz

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

如果您不喜欢这个方法，在我的博客上有很多随机数生成器（链接）。也许其中一个能满足您的需求。

- user448810

---

我喜欢这个实现方式，因为它不会溢出！谢谢。我想我会试一试。如果它像广告中所述的那样工作，它可能让我避免组合两三个较小范围的 RNG 调用。此外感谢您提供博客和文献的链接 - 在紧急情况下，我可以使用文献提供的示例之一。 - Carl Smotricz

@CarlSmotricz，这里有一个关于Park-Miller-Carter PRNG的优秀讨论和分析。Carter的优化显著提高了性能并降低了复杂度。该网站还讨论了将这个想法扩展到64位的可能性，允许您根据需要丢弃输出的高28位。 - Brett Hale

已经实现并且运行良好。我很感兴趣地阅读了这篇文章，但是直接采用了您上面的代码。由于我没有适用于36位版本的好常量，因此我使用了您的32位版本而没有进行更改。这一切都很好，因为我只需要25位。 - Carl Smotricz

Answer 2

只是一个简单的想法，我不知道这是否真的是最好的方法：您可以使用递归来生成具有不同质数p_i的12位3个LCG：

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

如果a不太大（比如12位），那么它永远不会溢出。然后，使用这三个12位随机数，您可以生成一个36位的随机整数：

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

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

困难在于要选择一个好的a。

无论如何，在使用之前，最好进行一些测试。

- Dr_Sam

---

我想知道我的奇怪脚本语言是否支持递归。我认为它是支持的，但由于过程除了通过副作用之外不返回其他值，所以编写这个递归解决方案可能会有些棘手！不过，基本思路是正确的；如果随机数生成器具有互质参数，我应该能得到一些漂亮的长周期。目前，我正在生成0..999范围内的2个数字，并将它们连接成我需要的6位数字，这样可以减少我的随机数生成器周期的一半，但这不是问题。不过，我仍在寻找更优雅的单调用解决方案。 - Carl Smotricz

好的，您可以将其实现为一个由3个12位整数或一个36位整数（您分解）组成的状态的单递归，以与其他答案相同的方式。无论如何，其他答案已经经过测试，所以肯定更好！ - Dr_Sam