c - 为什么在 rand 中使用 1103515245？

Question

我说的是 this来自 C 标准的 rand() 的实现非常简单:

static unsigned long int next = 1;

int rand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return (unsigned)(next/65536) % 32768;
}

来自 this Wikipedia article我们知道乘数 a(在上面的代码 a = 1103515245 中)应该只满足 2 个条件:

1. a - 1 可以被 m 的所有质因数整除。
   (在我们的例子中 m = 2^32，int 的大小，所以 m 只有一个质因数 = 2)
2. a - 1 是 4 的倍数，如果 m 是 4 的倍数。
   (32768是4的倍数，1103515244也是)

为什么他们选择了这样一个奇怪的、难以记住的“伙计，我受够了这些随机数，随便写什么”的数字，比如 1103515245？

也许有一些明智的理由，这个数字比另一个好？

例如，为什么不设置a = 20000000001？它更大、更酷、更容易记住。

Answer 1

如果你用LCG在d维空间上画点，它们最多位于(d!m)^1/_d 超平面。这是 LCG 的已知缺陷。

如果您不仔细选择 a 和 m(超出完全周期性的条件)，它们可能位于比这少得多的平面上。这些数字是通过所谓的光谱测试选出的。

“谱测试”(名称来自数论)是 d 维 union 分布所在的连续超平面之间的最大距离。对于尽可能多的 d，您希望它尽可能小。

参见 this paper对该主题进行历史回顾。请注意，您引用的生成器在论文中被提及(作为 ANSIC)并且确定不是很好。然而，高 16 位是可以接受的，但是许多应用程序将需要超过 32768 个不同的值(正如您在评论中指出的那样，周期确实是 2^31——维基百科链接中的完整周期性条件可能只是必要的).

ANSI文档中的原始源代码没有取高16位，产生的生成器很差，容易被误用(rand() % n 是人们首先想到的在 0 和 n 之间绘制一个数字，在这种情况下会产生非常非随机的结果。

另请参阅数值食谱中关于 LCG 的讨论。引用:

Even worse, many early generators happened to make particularly badchoices for m and a. One infamous such routine, RANDU, with a = 65539and m = 231, was widespread on IBM mainframe computers for many years,and widely copied onto other systems. One of us recalls as a graduatestudent producing a “random” plot with only 11 planes and being toldby his computer center’s programming consultant that he had misusedthe random number generator: “We guarantee that each number is randomindividually, but we don’t guarantee that more than one of them israndom.” That set back our graduate education by at least a year!