關於生成隨機浮點數的面試題？

01-01

int rantInt(); //隨機生成0或者1
int rantFloat(); //隨機生成均勻的0～1.0的浮點數
用rantInt()實現rantFloat()

IEEE-754 單精度浮點數有 23 位尾數（mantissa）。

那麼可以首先生成一個 $x in {0, 1, 2, ldots, 2^{23}-1}$ 的整數，然後再轉換成浮點數。

如果不想直接生操作 IEEE-754 格式，可使用除數：

float randFloat() { int x = 0; for (int i = 0; i &< 23; i++) x = (x &<&< 1) | randInt(); return (float)x / ((1 &<&< 23) - 1); }

但這個實現其實有非常輕微的不均勻問題，因為要生成 $[0, 1]$ 的 float，準確地應該要生成 $x in {0, 1, 2, ldots, 2^{23}}$ 的整數。然而，這個集合有 $2^{23}+1$ 個元素，不能用 23 個位來生成。

解決辦法之一，是簡單地使用 rejection sampling，用多一次 randInt() 生成 $y in {0, 1, 2, ldots, 2^{24} - 1}$ ，如果 $y > 2^{23}$ ，就棄掉此樣本，重新生成。

一般的偽隨機數生成器產生半閉區間 $[0, 1)$ 的輸出，而不是閉區間 $[0, 1]$ ，便不會有此問題。

Milo Yip 的答案有個問題，就是比較小的浮點數只能生成其中一部分，而所有小於2^-23的數肯定生成不出來。

假如我們有個更高的要求，就是所有滿足條件的浮點數都要以合適的概率被生成。

均勻的0-1之間的小數用二進位表示的話，所有的小數位是互相獨立的一半概率0一半概率1.

而浮點數的表達方式是 http://1.xxx*2^yyy 所以你需要做的是生成一個01序列，用來表示小數，比如

0.00100101110011....

所以你要做的就是生成小數點後的這個01序列，然後從第一個1開始取固定數目個作為那個xxx，前面0的個數用來計算yyy。

這個演算法應該是精確度和複雜度最優的了。

隨手寫個代碼：

double RandDouble() { int64 frac = 0; int64 exp = 1022; while(exp &>= 0 RandInt() == 0) { --exp; } if (exp &< 0) return 0.0; for (int i = 0; i &< 52; i++) { frac &<&<= 1; frac |= RandInt(); } double result; *reinterpret_cast&(result) = exp &<&< 52 | frac; return result; }

補充一下，之所以在意小數部分的精度是因為在很多情況下我們需要隨機生成一個0-1的均勻分布的x，然後計算y=F^{-1}(x)，比如y=arctan(1-x)。這時候x在小數的時候精度低會讓y在大數的部分分布很不均勻。

比如float精度是30位二進位小數（這裡的30是隨便說的……我不太確定float的二進位位是多少，剛查了下貌似是23位尾數），那生成30個0或1，然後放在小數點後面即可。

int rantFloat(){ float s=0 for (i=1;i&<=30;i++){ k=rantInt() s=s/2+k } return s }

看了下clang的&頭文件，generate_cannonical，就是生成一個[0,1)的浮點數

template& _RealType generate_canonical(_URNG __g) { const size_t _Dt = numeric_limits&<_RealType&>::digits; const size_t __b = _Dt &< __bits ? _Dt : __bits; #ifdef _LIBCPP_HAS_NO_CONSTEXPR const size_t __logR = __log2&::value; #else const size_t __logR = __log2&::value; #endif const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0); const _RealType _Rp = _URNG::max() - _URNG::min() + _RealType(1); _RealType __base = _Rp; _RealType _Sp = __g() - _URNG::min(); for (size_t __i = 1; __i &< __k; ++__i, __base *= _Rp) _Sp += (__g() - _URNG::min()) * __base; return _Sp / __base; }

核心部分就是取RAND_MAX，再生成一個隨機的整數，然後用整數除RAND_MAX

const _RealType _Rp = _URNG::max() - _URNG::min() + _RealType(1); _RealType __base = _Rp; _RealType _Sp = __g() - _URNG::min();

然後為了保證隨機性上述過程多重複幾次：

To generate enough entropy, generate_canonical() will call g() exactly k times, where k = max(1, ? b / log 2 R ?) and

b = std::min&(bits, std::numeric_limits&::digits)

R = g.max() - g.min() + 1.

如果已經有randomInt（感覺這個函數名取得不好，應該叫randomBit)，可以實現隨機整數，然後應該可以實現隨機浮點數。

來強答一發，歡迎大家相互討論。

這裡以C語言來答題。

首先要知道C語言一個float佔32個位元組，這32位元組是如何分布的那，如圖

其中第1位是符號位，指數位8位，這裡需要指出的是指數討論的範圍是-127—128（這裡以127為基準，即0111 1111表示0），即2^(-127)到2^(128)。由於是二進位表示，這裡舉個例子就明白了，例如8.5，8.5 = 1.0001 * 2^3，它在這32個位元組中可以表示為 0（符號位）1000 0010（指數位） 0001 0000 0000 0000 0000 0000（小數部分），這裡小數點前面的1不在32位的空間中表示。

那麼回到問題，在0，1之間，很顯然在float條件下，不可能表示所有的浮點數字。下面寫代碼來回答這個問題。

union {

float f;

int i;

} data;

void set1(int a, int n){

int i = 1;

i &<&<= n - 1;

a |= i;

}

float randFloat(){

for (int j = 24; j &<= 30; j++){

set1(data.i, j);

}

for(int j = 1; j &<= 23; j++){

if (randInt())

set1(data.i, j);

}

return data.f;

}

代碼很簡單，這裡就不解釋了。

什麼是均勻？

是數值上的均勻還是浮點數比特值的均勻？

姑且認為是前者吧

思路：

約定一個常數n，表示小數點後的數字數目。隨機生成一個n位數的大整數（小隨機數拼接而非相乘），然後除以十的n次方即可得結果

手機寫代碼。寫個思路。

簡單來說就是隨機出兩個無符號整型。

然後小的除去大的。

unsigned p = 0, q = 0

for i = 0 to sizeof(unsigned) :

p += randint() &<&< i, q += randint() &<&< i

return p&>q?q/p:p/q

就是不知道是否均勻…