如何在C中生成随机64位无符号整数

Question

我需要使用C.我的意思是产生的随机的64位无符号整数,范围应该0以18446744073709551615.RAND_MAX是1073741823.

我在链接中找到了一些可能重复的解决方案,但答案主要是连接一些rand()结果或进行一些增量算术运算.所以结果总是18位或20位.我也希望像成果5,11,33387,不只是3771778641802345472.

顺便说一句,我真的没有这么多的C经验,但任何方法,代码样本和想法都可能是有益的.

Answer 1

关于“所以结果总是 18 位或 20 位。”

请参阅@Thomas 评论。如果您生成足够长的随机数，代码将创建 5、11 和 33387 之类的数字。如果代码每秒生成 1,000,000,000 个数字，则可能需要一年时间，因为非常小的数字 < 100,000 在所有 64 位数字中非常罕见。

rand()简单返回随机位。一个简单的方法一次拉 1 位

uint64_t rand_uint64_slow(void) {
  uint64_t r = 0;
  for (int i=0; i<64; i++) {
    r = r*2 + rand()%2;
  }
  return r;
}

假设RAND_MAX在 OP 的情况下是 2 - 1 的某个幂1073741823 == 0x3FFFFFFF，利用每次生成30 至少 15位的优势。以下代码将调用rand()5 3次 - 有点浪费。相反，可以为下一个随机数保存移出的位，但这会带来其他问题。改天再说吧。

uint64_t rand_uint64(void) {
  uint64_t r = 0;
  for (int i=0; i<64; i += 15 /*30*/) {
    r = r*((uint64_t)RAND_MAX + 1) + rand();
  }
  return r;
}

便携式循环计数方法避免了15 /*30*/-但请参阅下面的 2020 编辑。

#if RAND_MAX/256 >= 0xFFFFFFFFFFFFFF
  #define LOOP_COUNT 1
#elif RAND_MAX/256 >= 0xFFFFFF
  #define LOOP_COUNT 2
#elif RAND_MAX/256 >= 0x3FFFF
  #define LOOP_COUNT 3
#elif RAND_MAX/256 >= 0x1FF
  #define LOOP_COUNT 4
#else
  #define LOOP_COUNT 5
#endif

uint64_t rand_uint64(void) {
  uint64_t r = 0;
  for (int i=LOOP_COUNT; i > 0; i--) {
    r = r*(RAND_MAX + (uint64_t)1) + rand();
  }
  return r;
}

此处评论的自相关效应是由弱rand(). C 没有指定特定的随机数生成方法。以上依赖于rand()- 或使用的任何基本随机函数 - 是好的。

如果rand()低于标准，则代码应使用其他生成器。然而，人们仍然可以使用这种方法来构建更大的随机数。

[编辑 2020]

Hallvard B. Furuseth提供了一种很好的方法来确定RAND_MAX当它是梅森数时的位数- 2 的幂减去 1。

#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
#define RAND_MAX_WIDTH IMAX_BITS(RAND_MAX)
_Static_assert((RAND_MAX & (RAND_MAX + 1u)) == 0, "RAND_MAX not a Mersenne number");

uint64_t rand64(void) {
  uint64_t r = 0;
  for (int i = 0; i < 64; i += RAND_MAX_WIDTH) {
    r <<= RAND_MAX_WIDTH;
    r ^= (unsigned) rand();
  }
  return r;
}

Answer 2

如果您不需要加密安全的伪随机数，我建议使用 MT19937-64。它是Mersenne Twister PRNG的 64 位版本。

请不要组合rand()输出，也不要建立在其他技巧之上。使用现有的实现：

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html