一个范围内的64位随机数

Question

因此，我一直在寻找一个函数，该函数需要2个参数，一个低值和一个高值（均为64位整数），而不是在这些范围之间生成一个随机数。我一直遇到的问题是，这个数字不是64位int，或者边缘的数字比中间的数字更常见。

这是一些代码：它只是一直返回-1或0…

#include<stdio.h>
#include<stdlib.h>
#include<inttypes.h>

int64_t range1=0,range2=18446744073709551614;

int64_t getRandomInRange(int64_t low, int64_t high )
{
    int64_t base_random = rand(); 
    if (RAND_MAX==base_random) return getRandomInRange(low, high);
    int range       = high-low,
        remainder   = RAND_MAX%range,
        bucket      = RAND_MAX/range;
    if (base_random < RAND_MAX-remainder) {
        return low+base_random/bucket;
    } else {
        return getRandomInRange(low, high);
    }
}

int main () {
    int i;
    for (i=0;i<100;i++) {
        printf("random number: %lld\n",getRandomInRange(range1, range2));
    }
}

Answer 1

您的代码返回 0 或 -1，因为18446744073709551614太大而无法放入int64_t。（事实上，它稍微太大而无法放入uint64_t，因为它正好是2⁶⁴，并且可以容纳k位无符号整数的最大数字是2^k-1。因此，您最终会得到有符号整数溢出。（gcc和叮当声（至少）警告过你，即使没有-Wall。

无论如何，如果您有某种机制来生成随机的64位无符号整数，那么生成您正在寻找的库函数并不困难。一个不错的选择是梅森图斯特图书馆。然而，为了进行演示，我们只能使用标准的C库函数，在本例中是< code>lrand48，它产生一个在< code>(0，2³¹-1)范围内均匀分布的整数。因为这个范围只产生31位的随机性，所以我们需要多次调用它才能产生64位。

#define _XOPEN_SOURCE
#include <stdlib.h>
#include <stdint.h>

uint64_t urand64() {
  uint64_t hi = lrand48();
  uint64_t md = lrand48();
  uint64_t lo = lrand48();
  return (hi << 42) + (md << 21) + lo;
}

要从范围[low， high）中获得无偏样本，我们需要将随机数生成限制为high-low的某个倍数。urand64的范围是大小2⁶⁴，因此我们需要排除modHigh-low264值。不幸的是，除非我们有一个长于64位的无符号int，否则我们实际上不能直接计算模。但是，我们可以使用标识：

modk（modkm modkn）=modk（m n）。

在这种情况下，我们将选择m作为264-1n作为1，以避免计算 。此外，很容易证明，除非 k是2的精确幂，否则 modk264-1 modk11不可能是2的确切幂，而如果 是2之精确幂，则所需的 modk264是0，其解释可在其他地方找到：

bool is_power_of_2(uint64_t x) {
  return x == x & -x;
}

因此，我们可以定义：

uint64_t unsigned_uniform_random(uint64_t low, uint64_t high) {
  static const uint64_t M = ~(uint64_t)0; 
  uint64_t range = high - low;
  uint64_t to_exclude = is_power_of_2(range) ? 0
                                             : M % range + 1;
  uint64_t res;
  // Eliminate `to_exclude` possible values from consideration.
  while ((res = urand64()) < to_exclude) {}
  return low + res % range;
}

请注意，在最坏的情况下，要排除的值的数量为2⁶³-1，略小于可能值范围的一半。因此，在最坏的情况下，我们平均需要两次调用urand64才能找到满意的值。

最后，我们需要处理这样一个事实，即我们被要求生成有符号整数，而不是无符号整数。然而，这并不是一个问题，因为必要的转换是定义良好的。

int64_t uniform_random(int64_t low, int64_t high) {
  static const uint64_t OFFSET = ((uint64_t)1) << 63;
  uint64_t ulow =  (uint64_t)low + OFFSET;
  uint64_t uhigh = (uint64_t)high + OFFSET;
  uint64_t r = unsigned_uniform_random(ulow, uhigh);
  // Conform to the standard; a good compiler should optimize.
  if (r >= OFFSET) return r - OFFSET;
  else             return (int64_t)r - (int64_t)(OFFSET - 1) - 1;
}

Answer 2

取模N不会导致均匀分布，除非N精确地划分范围R:

 rnd = 0..15,  range = 9.

 0 1 2 3 4 5 6 7 8  <-- 0..8 % 9 
 0 1 2 3 4 5 6      <-- 9-15 % 9
----------------------------------
 2 2 2 2 2 2 2 1 1    <-- sum = 16

同样，如果一个人试图通过乘以9/16来避免这个事实

 rnd = 0..15,   range = 9,   reducing function = rnd * 9 >> 4, one has
 0 1 2 3 4 5 6 7 8    for rnd = 0, 2, 4, 6, 8, 9, 13, 15    and
 0 1 2 3   5 6 7      for rnd = 1, 3, 5, 7, 10, 12, 14
------------------------
 2 2 2 2 1 2 2 2 1     <-- sum = 16

这就是所谓的“鸽子洞原理”。

创建随机数均匀分布的一种正确方法是生成随机数的ceil（log2（N））位，直到这些位表示的数字小于范围：

 int rand_orig(); // the "original" random function returning values from 0..2^n-1
                  // We assume that n = ceil(log2(N));
 int rand(int N)
 {
     int y;
     do {
          y = rand_orig();
     } while (y >= N);
     return y;
 }

这当然可以改进，如果rand_orig（）；将返回更大的值n

另一种方法是创建一个平衡值（N

 #define CO_PRIME 1 // Better to have some large prime 2^(n-1) < CO_PRIME < 2^n-1
 int rand_orig();   // some function returning random numbers in range 0..2^n-1
 int rand(int N)    // N is the range
 {
     static int x;
     int y = rand_orig();
     int new_rand = (x + y) % N;
     x = (x + CO_PRIME) % N;
     return new_rand;
 }

现在这个平衡项x的周期是N，导致至少均匀分布。