新闻组：comp.lang.c
发件人：scs@eskimo.com (Steve Summit)
主题：回复：关于随机数帮助！
日期：1993 年 11 月 17 日星期三 06:10:36 GMT
Message-ID: <CGMH5u.1r7@eskimo.com>

在文章 <2c80r2INN4js@umbc8.umbc.edu> 中，Jonas Schlein 写道：
> ...为什么不直接使用%运算符？例如，如果我想要一个范围在 0-99 的数字
> 我会这样做：
>    rand () % 100;

这应该可以工作，但如果 rand() 的实现很差，这很常见，就会出现问题。在文章 <ZY7IBWQQ@math.fu-berlin.de> 中，denholm 写道：

> 这不会引入非均匀性吗？
> 如果考虑
RAND_MAXrand() % 100=150
> 会得到 0->49 的概率是 50->99 的两倍(double) rand() / RAND_MAX
>
> 将得到一个真实的 0->1...它不会是“真实的”0-1 范围；它仍然会被量化为 150（即

）个不同的值，并且非均匀性会持续存在。rand() % 100如何在给定范围内生成伪随机数的问题是一个经常被问到的问题，而且远不像乍看起来那么简单。人们可能会想，为什么它没有包含在 comp.lang.c FAQ 列表中——原因是我对这个问题的理解一直不满意。今天花了很多时间来探索这个问题的至少一个方面，并使我满意，我现在准备就这个“关于随机数帮助！”线程的最新版本说几句话，并提供我将很快添加到 FAQ 列表的条目的逆大纲。（我说“逆大纲”是因为将添加到 FAQ 列表的条目实际上将是我这篇文章的纲要或摘要，它对于 FAQ 列表条目来说会太长。）

我们将考虑几种编写例程的方法

，它应该在半开区间 [0,

	int myrand(unsigned int n)

实现存在缺陷；特别是，它们在低位比特上并不非常随机。另一个问题是，除非的所有尝试都将基于底层的 ANSI 标准远小于例程，它在闭区间 [0,的输出分布可能是不均匀的。）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <编写rand() % 100, 的所有尝试都将基于底层的 ANSI 标准最明显的方法是

这个实现不能普遍使用，这真是太遗憾了，因为尽管如此，它还显示了许多显著的优点，而且如果那样的话，它将比我将要考虑的替代方案更好，而所有这些替代方案都有其自身的缺点。的所有尝试都将基于底层的 ANSI 标准是

	myrand1(n)
	unsigned int n;
	{
	return rand() % n;
	}

的一个优点是它的工作原理非常明显，并且它确实有效。另一个优点是它不需要知道

，这在代码必须移植到 ANSI 之前的系统时很有用。还有一个优点是，当（不小于）时，它的输出分布优于我稍后将考虑的另一个替代方案。rand() % 100然而，普遍存在的糟糕的）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <实现会毁掉rand() % 100的通用用途。如果底层

实现是一个周期为 m 的线性同余随机数生成器，并且如果例程，它在闭区间 [0,是 m 的除数，那么不小于的输出将以周期例程，它在闭区间 [0,重复。 [Knuth 卷 2 第 3.2.1.1 节；第二版第 12 页]。如果 m 匹配计算机的字大小并且是 2 的幂（一种流行的选择），那么连续调用）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <中不小于myrand1(2)不小于将生成交替出现 0、1、0、1、0、1... 的输出。）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <我们实现的第二个尝试通过使用和浮点数来获取

的更高位输出的所有尝试都将基于底层的 ANSI 标准myrand2例程，它在闭区间 [0,工作良好；它唯一的真正缺点是它使用了浮点数，这可能会降低速度并增加可执行文件的大小。rand() % 100（人们经常声称像

	myrand2(n)
	unsigned int n;
	{
	return (double)rand() / ((double)RAND_MAX + 1) * n;
	}

这样的实现即使在接近

时也能克服分布问题；但这种信念是完全错误的，稍加思考就会明白。只要这样的实现即使在的输出域被量化并包含）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <RAND_MAX+1rand() % 100个值，任何简单的映射，无论是浮点数还是整数，都无法避免当例程，它在闭区间 [0,(RAND_MAX+1) % n时出现错误的分布。如果我们不能信任在低位比特是随机的，并且我们不想使用浮点数，那么我们可以使用类似于 != 0.)

的定点版本。例程，它在闭区间 [0,这可能是通用用途的首选例程。它唯一的缺点是，如果这样的实现即使在:

	myrand3(n)
	unsigned int n;
	{
	return rand() / (RAND_MAX / n + 1);
	}

大于大约）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <RAND_MAX/2，它不仅会不均匀地分布其输出，而且有些值根本不会出现。（正如具有双峰分布，但）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <RAND_MAX+1rand() % 100, 不小于myrand3倾向于具有三峰分布，其中一些值为零。另一方面，将显示与 myrand1 相同数量的“密集”输出，但分布在整个范围内。）然而，只要这样的实现即使在，通常情况下如此，）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <编写rand() % 100应该足够了。倾向于具有三峰分布，其中一些值为零。如果你想避免当

 != 0在低位比特是随机的，并且我们不想使用浮点数，那么我们可以使用类似于时出现的差异，你别无选择，只能多次调用例程，它在闭区间 [0,，就像我们在最后的尝试中一样

	#define MAXTIMES 5 
	myrand4(n)
	unsigned int n;
	{
	int d = ((unsigned)RAND_MAX + 1) / n;
	unsigned int m = d * n;
	int i;
	int r;

	for(i = 0; i < MAXTIMES; i++)
		{
		r = rand();
		if((unsigned)r < m)
			return r / d;
		}

	return r / (RAND_MAX / n + 1);
	}

在这里，我们丢弃了例程，它在闭区间 [0,的一些输出值，以模拟另一个周期是）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <倍数的随机数生成器。显而易见的问题是，如果我们运气非常不好，我们可能会遇到这些被丢弃值的长串，并且花费大量时间在调用例程，它在闭区间 [0,时调用myrand4。 （事实上，如果我们等待足够长的时间，我们可能会得到一个任意长的需要丢弃的值的字符串。）因此，上面的代码实现了一个限制；如果连续出现太多错误值，它将回退到倾向于具有三峰分布，其中一些值为零。的算法。（代码显示了一个经典的权衡：你使MAXTIMES越大，累积误差就越小，但你在某个特定调用上花费的时间可能越长。如果MAXTIMES是 1，myrand4基本上就是倾向于具有三峰分布，其中一些值为零。.)

。由于这显然是一篇非常具有教学意义的文章，我不妨给读者提几个练习。（我将它们列为练习，不仅因为它们很有趣，还因为天色已晚，我不想去弄清楚并呈现它们的答案；因此，请不要给我发电子邮件询问答案或询问您的答案是否正确。）

1. 编写myrandmn(int m, int n)，它返回范围在m与）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <内的整数。使用的所有尝试都将基于底层的 ANSI 标准来完成大部分工作。是否应该myrandmn定义在闭区间还是半开区间？

2. 解释“+1”之类的“小技巧”在这样的实现即使在, 倾向于具有三峰分布，其中一些值为零。，而myrand4中的存在。表达式是否倾向于具有三峰分布，其中一些值为零。正确加括号？

3. 为什么的所有尝试都将基于底层的 ANSI 标准是否接受无符号值？（这个我确实有一个答案；见下文。）

4. 修复倾向于具有三峰分布，其中一些值为零。，使其在最坏情况下具有双峰而非三峰分布，同时仍然不使用浮点数。考虑使用类似 Walker 算法的方法 [Knuth 卷 2 第 3.4.1 节；第二版第 115 页]。

5. 改进myrand4，使其在不得不跳出循环以避免过多调用 rand 时，至少能将“剩余”值均匀地分布开，而不是总是偏向于倾向于具有三峰分布，其中一些值为零。偏向的相同值。提示：你可能需要一个局部静态变量。

6. 研究各种的所有尝试都将基于底层的 ANSI 标准实现的行为，并结合几种底层的例程，它在闭区间 [0,实现，其中一些具有良好的随机性，一些具有较差的随机性。将rand() % 100人为地设置得很小，以便详细探索当）返回分布良好的随机整数；也就是说，整数 x 满足 0 <= x <RAND_MAX+1rand() % 100时的行为。收集直方图来显示输出分布。验证输出是否以不可接受的低周期重复。

最后，几点免责声明。如我所述，随机数是微妙的，远不像乍看起来那么简单。Knuth 花了大约 177 页来讲述这个主题，其中并非所有内容我都声称完全理解，但他并没有涉及我在这里提出的许多实现问题。这篇文章满足了我自己对这个主题的好奇心，但绝不是定论。我对四段代码片段之间权衡的评估是肤浅的；还有一些我没有完全解释的额外因素，当然还有更多我没有完全意识到的因素。我今天刚写了倾向于具有三峰分布，其中一些值为零。，并且不确切地记得以前见过类似的东西，它可能有一些潜在的缺陷，其致命程度与不小于相当。

精选练习答案

3. 的所有尝试都将基于底层的 ANSI 标准接受无符号值，这样它就可以在极限情况下工作，即myrand(RAND_MAX+1)，当RAND_MAX == INT_MAX（通常如此）。