为什么1103515245兰德使用？ [英] Why 1103515245 is used in rand?

问题描述

我说的是这个的出奇的简单执行兰特（）与C标准​​：

I'm talking about this surprisingly simple implementation of rand() from the C standard:

static unsigned long int next = 1;

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

维基百科文章我们知道乘数 A （以上code A = 1103515245 ）应履行只有2个条件：

From this Wikipedia article we know that the multiplier a (in above code a = 1103515245) should fulfill only 2 conditions:

1. A - 1 按 M 的所有素因子整除结果。
   （在我们的例子 M = 2 ^ 32 中，i​​nt的大小，因此 M 只有一个素因子= 2 ）


2. A - 1 是4的倍数，如果 M 是4.结果的倍数
   （32768是4，和1103515244多个太）

1. a - 1 is divisible by all prime factors of m.
   (In our case m = 2^32, size of the int, so m has only one prime factor = 2)
2. a - 1 is a multiple of 4 if m is a multiple of 4.
   (32768 is multiple of 4, and 1103515244 too)

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

也许有一些聪明的原因，这个数字在某种程度上比其他的更好吗？

Maybe there are some wise reasons, that this number is somehow better than the other?

例如，为什么不设置 A = 20000000001 ？这是更大的，长得帅，更容易记住。

For example, why don't set a = 20000000001? It's bigger, cool-looking and easier to remember.

推荐答案

如果您使用的是LCG来在D维空间画点，他们会趴在，至多m ^{1 / <子> D} 超平面。这是装码组的已知缺陷。

If you use a LCG to draw points on the d dimensional space, they will lie on at most m^1/_d hyperplanes. This is a known defect of LCGs.

如果你不仔细选择了和M（超出全周期的条件），他们可能会趴在比飞机少得多。这些数字是由所谓的光谱测试选定的

If you don't chose carefully a and m (beyond the condition for full periodicity), they may lie on much fewer planes than that. Those numbers have been selected by what is called the spectral test.

在光谱测试（名字来源于数论）是其d维联合分布连续撒谎超平面之间的最大距离。你希望它是尽可能小尽可能多ð，你可以测试一下。

The "spectral test" (the name comes from number theory) is the maximum distance between consecutive hyperplanes on which d-dimensional joint distributions lie. You want it to be as small as possible for as many d as you can test.

请参阅this有关该主题的历史回顾文章。请注意，您引用发电机在论文中提到（如ANSIC），并视为不太好。高阶16位是接受的，但，但许多应用程序将需要超过32768不同的值（如你在评论中指出，周期确实是2 ^ 31 - 在维基百科的链接，全周期的条件可能只需要）

See this paper for a historical review on the topic. Note that the generator you quote is mentioned in the paper (as ANSIC) and deemed as not very good. The high order 16 bits are acceptable however, but many applications will need more than 32768 distinct values (as you point out in the comments, the period is indeed 2^31 -- the conditions for full periodicity in Wikipedia's link are probably only necessary).

在ANSI文件中的原始出处code没有采取高位16位，产生一个非常贫穷的发生器，它是很容易误用（兰特（）％N 是人们首先想到的画 0 和 N ，这会产生一些非常不乱在这种情况下）。

The original source code in the ANSI document did not take the high order 16 bits, yielding a very poor generator which is easy to misuse (rand() % n is what people first think of to draw a number between 0 and n, and this yields something very non random in this case).

又见于数字食谱装码组的讨论。引用：

See also the discussion on LCGs in Numerical Recipes. Quoting:

更糟糕的是，许多早期的发电机发生做出特别糟糕
  选择m和一个。一个臭名昭著等日常，RANDU，具有= 65539
  和M = 231，是在IBM大型机多年wides $ P $垫，
  和广泛复制到其他系统。我们中的一位回忆作为毕业
  学生产生随机​​的情节，只有11架飞机和被告知
  由他滥用了他的计算机中心的规划顾问
  随机数发生器：我们保证每个数是随机
  个别地，但我们不保证他们的多于一个是
  随机的。这至少每年重新设置我们的研究生教育！

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

这篇关于为什么1103515245兰德使用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！