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

36位的补码整数
算术限于+，-，*，/和余
的环境中编写的应用程序没有像AND或OR这样的操作。但由于补全，XOR相当于减法和NOT否定。
数字溢出是致命的，所以不能用于静默截断
是的，有条件：IF/THEN/ELSEIF/ELSE/IF。

理想情况下，我想35或36位随机整数，但25位就足够了。

linear congruential generator我的天真实现如果基于足够大的数字并且在使用较小的数字时只产生少量的比特就会溢出。

因此，我正在寻找一组数字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

万一有人关心，脚本语言是SSG（符号流发生器）在UNISYS 2200大型机操作系统称为EXEC 8.

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

来源

2013-02-14 Carl Smotricz

你有条件吗？ – Pubby 2013-02-14 11:40:22

通过运行现在生成的种子价值，您可以改进现有产品。 – 2013-02-14 12:27:56

@Pubby：是的，有IF/THEN/ELSE/ENDIF。我要更新我的问题以反映这一点，谢谢！ – 2013-02-14 12:43:29

它可以编写一个线性同余随机数发生器，可以永远不会溢出，斯蒂芬K.公园和Keith W.米勒demonstrate在他们的论文随机数生成器：好的很难找到：

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部分，最后的随机数是通过求和部分产生的。

如果你不喜欢那样，我在我的博客上有随机数发生器的lots。也许其中一个会做你想做的。

来源

2013-02-14 14:55:03 user448810

我喜欢这种实现它的防溢性！谢谢。我想我会给这个旋转。如果它按照广告方式工作，它可能会让我避免将2或3个呼叫组合到更小范围的RNG。也感谢您的博客和论文的链接 - 我可以使用本文提供的众多示例之一。 – 2013-02-14 15:37:17

@CarlSmotricz，对[Park-Miller-Carter]（http://www.firstpr.com.au/dsp/rand31/）PRNG有很好的讨论和分析。卡特的优化大大提高了性能，并降低了复杂性。该网站还讨论了将思路扩展到64位，允许输出的高28位被丢弃以满足您的需求。 – 2013-02-14 16:57:37

实现并像魅力一样工作。我有兴趣阅读文章，但直接从上面采用了你的代码。由于我对36位版本没有很好的常量，因此我使用的是32位版本。这很好，因为我只需要25位。 – 2013-02-18 07:52:06

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

X_I（N）=一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-14 14:22:35

我不知道我的奇怪的脚本语言“做”递归。我认为它确实如此，但由于程序不会通过副作用返回值，因此递归编写此解决方案可能会非常棘手！尽管如此，基本的想法是合理的。如果RNG具有互质参数，我应该得到一些很好的长周期。目前，我在0..999范围内生成2个数字，并将它们连接成我需要的6位数字，这将我的RNG时间减半，但不是问题。尽管如此，我仍然在寻找更优雅的单通电话解决方案。 – 2013-02-14 15:23:43

那么，你可以将它作为一个单一的递归实现，其状态由3个12位整数或一个36位整数（你分解）组成，与其他答案一样。无论如何，其他答案已经过测试，所以更好！ – 2013-02-14 16:07:57

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

回答

相关问题