64位隨機數在一個範圍內

Question

所以我一直在尋找一個函數，它需要兩個參數一個低值和一個高值（都是64位整數），而不是在這些範圍之間生成一個隨機數。我一直遇到的問題是數字不是64位整數。或者邊緣的數字比中間的數字更普遍。

下面是一些代碼：它只是不斷返回-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

隔空模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 

同樣，如果試圖通過乘以eg來避免這個事實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 

這就是所謂的'鴿子洞原則'的行動。

一種適當的方式來創建隨機數的均勻分佈是生成小區（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 >> log（N）均勻分佈;那麼只需丟棄大於N的最大倍數的rand_orig（）的值並用模數減小範圍就足夠了。另一種方法是創建一種將值（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，從而導致至少均勻分佈。

Answer 2

您的代碼返回0或-1，因爲18446744073709551614太大而不適合int64_t。 （實際上，它太大而不適合uint64_t，因爲它恰好是2 ，並且可以填入k位的最大數位無符號整數是2 ^k -1。）所以你最終與有符號的整數溢出。 （即使沒有-Wall，gcc和clang（至少）也會警告您。）

無論如何，生成您正在尋找的庫函數並不困難，只要您有一些機制來生成隨機的64位字符串，位無符號整數。一個好的選擇是Mersenne Twister library。但是，對於演示，我們只能使用標準C庫函數，在這種情況下，lrand48會生成範圍爲(0, 231-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值。不幸的是，除非我們有一個unsigned int長度超過64位，否則我們實際上不能直接計算模數。但是，我們可以使用以下標識：

modk(modkm + modkn) = modk(m+n)。

在這種情況下，我們會選擇m爲264-1和n爲1，以避免計算modhigh-lown。另外，很容易證明，除非k是2的精確冪，否則modk264-1 + modk1不可能完全是k，而如果k是2的精確冪，則期望的modk264是0。我們可以使用以下簡單測試2的冪，其解釋可以在其他地方找到：

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 ，略低於h以及可能值的範圍。因此，在最糟糕的情況下，我們需要平均兩次撥打電話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; 
}