特殊的简单随机数生成器

Question

如何创建一个函数，在每次调用时生成一个随机整数？该数字必须尽可能随机（根据均匀分布）。只允许使用一个静态变量和最多3个基本步骤，其中每个步骤仅包含1或2元的基本算术运算。

例子：

int myrandom(void){
  static int x;
  x = some_step1;
  x = some_step2;
  x = some_step3;
  return x;
}

基本算术运算包括加、减、取余、按位非、按位异或、按位或、左移、右移、乘法和除法。当然，不允许使用rand()、random()或类似的函数。

- psihodelia

---

这是一个没有价值的面试问题。它要求你提供你所知道的东西（或可能知道的，或者你可能只是在杂志上读到的），而不是你能够做到的（或能够推断出来的，或者能够进行推理的）。 - Patrick

#1，这只是一个玩笑。 #2，谁说返回相同的数字不是随机的呢？ - KevinDTimm

需要指出的是，3在范围（3）上分布良好。 - LanceH

一个好的随机数生成器是一个非常非常困难的问题。除非应聘者已经有很多相关经验和背后的数学知识，否则他们不可能提出任何合理的东西。“生成随机数的过程太重要了，不能靠机会。”- Robert R. Coveyou - whatsisname

@Patrick，这可能用于了解求职者如何应对问题较差的情况 -毕竟，没有一份工作是只会问出良好的问题的... - AakashM

Answer 1

线性同余生成器是最古老和最简单的方法之一：

int seed = 123456789;

int rand()
{
  seed = (a * seed + c) % m;
  return seed;
}

只需要使用基本算术操作，就能完成这个算法。

请注意，仅当以特定方式选择 a 、 c 和 m 时，此算法才能正常工作！

为了确保此序列的最长可能周期， c 和 m 应该是互质的， a - 1 应该可以被 m 的所有质因数整除，并且如果 m 可以被4整除，则也应该可以被4整除。

一些示例参数在维基百科上有展示：例如ANSI C编译器提出m = 2^31, a = 1103515245，c = 12345。

- Jack

---

@psihodelia - 那么'int seed = 123456789;'是什么意思？ - KevinDTimm

最古老、最簡單和絕對最差的之一。 - Alexandre C.

我是通过间接的方式来到这里的，因此为了未来的读者，我想补充一下：这非常接近 rand() 的参考实现。 - std''OrgnlDave

我尝试了这个算法，使用建议的m、a和c值。对于任何种子，它都会生成交替的奇数和偶数。如果我使用random%2生成随机标志序列，我最终只会得到1、0、1、0、1、0等。 - Atul

请注意，如果对2的幂取模，则此操作将生成{0,1，...，n-1}的循环模n序列，正如@Atul所提到的那样。 - Mateen Ulhaq

Answer 2

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

种子不能为0。来源：http://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.VlcaYzKwEV8

更多信息请参见维基百科：https://en.wikipedia.org/wiki/Xorshift

- misioptysio

---

这个解决方案中的“随机性”在哪里？ - Gian Paolo

“随机性”在于异或操作翻转了位移的位“随机地” :). 为此，我们需要至少设置一个位，这就是种子不能为零的原因。 - misioptysio

这种解决方案在CPU周期方面似乎更便宜：没有乘法，没有除法-可能对于密集生成有用。 - misioptysio

我现在明白了（如果我没错的话），这里的x是先前生成的随机数，对吧？ - Gian Paolo

抱歉耽搁了。是的，那个x是一个种子/之前生成的数字，因此根据生成规则，下一个值是通过对先前的值使用简单算术运算得到的。 - misioptysio

Answer 3

你可以看一下这个链接。它并不是一个完美的随机数生成器，但就我所知，它确实满足你的要求。

在这里，你可以找到更多关于随机数生成的信息。

- phimuemue

Answer 4

这是一个在整个int范围内具有均匀分布的函数：

int rand()
{
  static int random = 0;
  return random++;
}

- Bill

---

不是随机的：其生成规则容易被识别，因此它不算是随机的（而是非常糟糕的伪随机）。 - ShinTakezou

@Shin：我从未声称这是一个好的伪随机数生成器，只是说它是一个伪随机数生成器。 :P - Bill

@Shin：你计划如何证明任何特定的解决方案是“最随机可能”的解决方案？ - Bill

@Shin：一种完全有效的随机数生成器（基于物理原理）将产生所有此类递增数列！序列越长，您需要等待的时间就越长，但请自行尝试。选择任何您认为可以的随机数源，并开始在其中寻找递增序列。准备感到惊奇 :) 提示：获取任意长度的递增序列的概率是非零的。这就是区分PRNG和真正的RNG的方法。PRNG永远不会生成某些序列，而真正的RNG会生成。 - Kuba hasn't forgotten Monica

实际上，判断您是否正在处理PRNG的一个简单方法（通常）是选择任意一串数字序列，并检查平均而言是否“足够频繁”出现。随着序列长度的增加，最终会遇到PRNG永远不会产生的序列，而真正的随机数源将按照理论预期产生它们。我怀疑您从未真正观察过真正随机的数字序列。在较短的长度下，它们看起来相当“非随机”。 - Kuba hasn't forgotten Monica

Answer 5

Boost有一个非常好的随机数库，源代码也是公开的，所以你可以尝试在那里查找并使用你需要的内容（即剪切和粘贴）。

- andand

Answer 6

如果我输入 man rand，我可以阅读 POSIX.1-2001 中提供的实现 rand() 和 srand() 的可能示例。例如，请参见此处。如果你需要更复杂的东西，请看看GNU科学库；当然，你可以下载代码并查看实现。

- ShinTakezou

Answer 7

我猜这对于大范围来说已经足够好了，但我还没有使用过。两个数字必须互质。

u32 rand()
{
  static u32 seed = 3459173429;
  seed = 910230123 + seed ;
  return seed;
}

工作示例

int printf(char* , ...);

typedef unsigned int u32;
typedef   signed int i32;

u32 rand()
{
  static u32 seed = 3459173429;
  seed = 910230123 + seed ;
  return seed;
}

i32 randInt(i32 a, i32 b)
{
  return (rand() % (b - a)) + a;
}

void main()
{
  for(int i = 0 ; i < 10000 ; i += 1)
  {
    printf("%d\n", randInt(-50, 50));
  }
}

- raoof

Answer 8

我使用这个

SUBROUTINE GNA(iiseed)
    USE Variaveis
    parameter (ia=843314861,ib=453816693,m=1073741824, r231=1./2147483648.)
    INTEGER :: iiseed

    iiseed = ib + ia*iiseed
    if (iiseed.lt.0) iiseed = (iiseed+m) + m
    RndNum = iiseed*r231

END SUBROUTINE GNA

在编程中，可以通过不为程序中每次调用随机数生成器创建一个新的随机数生成器来实现更大的随机性收益，而无需花费更多的计算时间。

这是一个非常好的技巧！

- Denis da Mata