Boost 隨機數庫：概念

隨機數生成庫：概念

簡介

許多應用領域都需要用到隨機數，例如：

數字控制 (模擬, Monte-Carlo 算法)
遊戲 (敵人的行為應該是不確定的)
安全 (秘匙生成)
測試 (白盒測試中的隨機覆蓋)

Boost 隨機數生成庫框架中的隨機數生成器具有良好的性質，因此它們可以用於數字控制和安全領域。關於數字控制中隨機數應用的介紹，參看：

"Numerical Recipes in C: The art of scientific computing", William H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992, pp. 274-328

以下幾種隨機數生成器對應於不同的應用領域：

不確定隨機數生成器
偽隨機數生成器
擬隨機數生成器

所有的變體都具有一些共同的性質，這些 (STL) 概念叫做 NumberGenerator 和 UniformRandomNumberGenerator。每一種概念都將在相應節中予以定義。

本庫的目標是：

簡化第三方隨機數生成器的集成
定義生成器的檢驗接口
為常見分佈提供易用的前端類
提供盡可能高的效率
控制前端處理中的量子化 (quantization) 問題 (未完成)

數字生成器 (Number Generator)

數字生成器是取 0 個參數的 函數對像 (std:20.3 [lib.function.objects])。調用 operator() 返回一個數字。下表中，X 是返回類型 T 的數字生成器類，u 是 X 的實例。

`NumberGenerator` 需求
表達式	返回類型	前/後條件
`X::result_type`	T	`std::numeric_limits<T>::is_specialized` 為真；`T` 為 `LessThanComparable`
`u.operator()()`	T	-

注意：NumberGenerator 需求並未對返回值的性質作任何限定。

均勻隨機數生成器 (Uniform Random Number Generator)

一個均勻隨機數生成器是一個 NumberGenerator，它能提供在給定值域內均勻分佈的隨機數序列。這一值域可以是編譯時就確定的；也可以是 (僅) 在運行時生成器構建之後才可知的。

有窮集 S 的 緊下界 是 S 中的唯一元素 l，滿足：對 S 中的任意元 v，l <= v 成立。類似地，有窮集 S 的 緊上界 是 S 中的唯一元素 u，滿足：對 S 中的任意元 v，v <= u 成立。

下表中，X 是返回類型 T 的均勻隨機數生成器類，v 是 X 的 const 實例。

`UniformRandomNumberGenerator` 需求
表達式	返回類型	前/後條件
`X::has_fixed_range`	`bool`	編譯時常量；若為 `true`，隨機數均勻分佈的值域在編譯時是可知的，成員 `min_value` 和 `max_value` 存在。注意：由於編譯器的限制，這一標誌可能為 `false`。
`X::min_value`	`T`	編譯時常量；`min_value` 等於 `v.min()`
`X::max_value`	`T`	編譯時常量；`max_value` 等於 `v.max()`
`v.min()`	`T`	`operator()` 可能返回的值的緊下界。此函數的返回值在 v 的生存期內不會改變。
`v.max()`	`T`	若 `std::numeric_limits<T>::is_integer` 為真，則為 `operator()` 可能返回的值的緊上界；否則為大於該緊上界的最小可表示數字。此函數的返回值在 v 的生存期內不會改變。

成員函數 min, max, 和 operator() 的均攤時間複雜度應當是常數。

注意：對於整數生成器 (即 T 為整數類型)，生成的值 x 滿足 min() <= x <= max()；對非整數生成器 (即 T 為非整數類型)，生成的值 x 滿足 min() <= x < max()。
理論注記：min 和 max 所描述的值域有兩個用途。首先，借助它可以把生成的值縮放到某個「正規」的值域內，如 [0..1)。其次，它描述了生成值的有效位數，後者在進一步處理過程中可能會有用。
對於整數，值域是閉區間 [min,max]，因為現有的整數類型可能無法表示半開區間 [min,max+1) (譯註：即 max+1 可能超出某一整數類型的上限)。對於非整數，值域是半開區間 [min, max)，因為作此規定在處理連續分佈的邊界情況時更為方便。

注意：UniformRandomNumberGenerator 概念並不需要 operator()(long) 因此不滿足 RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]) 需求。如果需要，應該使用 random_number_generator。
理論注記：沒有提供 operator()(long)，因為把某些生成器產生的結果從一個整數值域映射到另一個整數值域會帶來開銷。

不確定均勻隨機數生成器 (Non-deterministic uniform random number generator)

一個不確定均勻隨機數生成器是一個 UniformRandomNumberGenerator，它基於某種隨機過程，因此能提供「真正隨機的」的隨機數序列。隨機過程包括原子核衰變、Zehner 二極管的噪音、量子隧道效應、投擲骰子、罐中取物、投擲硬幣等等。網絡數據包到達的間隔、鍵盤事件有時也可以被看作隨機過程。

random_device 類是不確定隨機數生成器的一個模型。

注意：這種隨機數生成器可以用於安全應用，從而避免入侵者「猜出」程序所生成的隨機數，從而竊取密碼或者認證密鑰。因此，這一概念的模型必須小心設計，不能洩露與環境有關的任何信息。例如，及時清除臨時數據可能是很恰當的。

偽隨機數生成器 (Pseudo-random Number Generator)

一個偽隨機數生成器是一個 UniformRandomNumberGenerator，它根據某一算法和內部狀態提供確定的偽隨機數序列。線性同余和反向同餘生成器 (linear congruential and inversive congruential generators) 屬於此類生成器。此類生成器的行為往往在很大程度上取決於其參數。為檢查出錯誤的實現，應該提供一個外部測試套件來檢查所產生的序列和驗證值相符。

Donald E. Knuth 在其著作 "The Art of Computer Programming, Vol. 2, 3rd edition, Addison-Wesley, 1997" 中給出了偽隨機數生成的綜述。對各個生成器的描述將分別指出其參考資料。

注意：因為偽隨機數生成器的狀態是有窮的，生成器返回的數字序列最終總會陷入循環。

偽隨機數生成器的需求是 UniformRandomNumberGenerator 需求的超集。下表中，X 是返回類型 T 的偽隨機數生成器類，x 是 T 的實例，u 是 X 的實例，v 是 X 的 const 實例。

`PseudoRandomNumberGenerator` 需求
表達式	返回類型	前/後條件
`X()`	-	創建一個生成器，其初始狀態取決於實現。注意：用這種方法創建的多個生成器實例可能產生有關或者相同的隨機數序列。
`explicit X(...)`	-	創建一個生成器，其初始狀態由用戶提供；構造函數的參數由實現確定。
`u.seed(...)`	void	根據參數設置當前狀態；至少要提供一個與非默認構造函數簽名式相同的 `seed` 函數。
`X::validation(x)`	`bool`	把 `x` 和隨機數序列的第 10001 個元素相比，後者是預先計算出來並硬編碼的。生成器必須使用默認構造函數構建，並且沒有調用 `seed`，以確保驗證是有意義的。

注意：seed 成員函數與 STL 容器的 assign 成員函數類似，儘管後者的命名不太恰當。

偽隨機數生成器的模型類也必須是 EqualityComparable 的模型，即實現 operator==。若從給定狀態出發，兩偽隨機數生成器返回相同的數字序列，則稱它們等價。

偽隨機數生成器的模型類也應當是 Streamable 概念的模型，即實現 operator<< 和 operator>>。若實現，operator<< 把偽隨機數生成器的當前全部狀態寫入給定的 ostream 中；operator>> 用於其後恢復狀態。狀態應該以平台無關的方式寫入；但可以假設讀寫時 locales 是相同的。恢復後的偽隨機數生成器和原生成器應等價。

偽隨機數生成器的模型類也可以是 CopyConstructible 和 Assignable 概念的模型。但請注意，原生成器和其副本是完全相同的，因此對於有些應用領域可能會不恰當。因此，不鼓勵複製偽隨機數生成器；它們總應以 (非 const) 引用傳遞。

rand48, minstd_rand 和 mt19937 類是偽隨機數生成器的模型。

注意：此類偽隨機數生成器可用於數字控制、遊戲和測試。取不少於一個參數的構造函數和 seed() 成員函數可以讓用戶設定狀態；在調試 Monte-Carlo 算法、分析特定的測試場景 (test scenario) 時這是很有用的。Streamable 概念允許保存和恢復生成器的狀態，例如隔一段時間後重新運行某一測試套件。

隨機分佈 (Random Distribution)

隨機分佈取均勻分佈的隨機值作為輸入，輸出符合某一分佈的隨機數。下表中，X 是返回 T 類型的隨機分佈類，u 是 X 的實例，x 是 X 的實例 (可為 const)，e 是任一均勻隨機數生成器類型的左值，返回類型是 U。

Random distribution 需求 (以下，加上 Number Generator, `CopyConstructible` 和 `Assignable`)
表達式	返回類型	前/後條件	複雜度
`X::input_type`	U	-	編譯時求值
`u.reset()`	`void`	此後對 `u` 的使用將不受調用 `reset` 前 `e` 產生的數字序列的影響。	常數
`u(e)`	`T`	使用同一對像 `e` 反覆調用產生的隨機數序列將按某一概率密度函數 p(x) 隨機分佈。	(均攤) 對 `e` 的調用的複雜度的常數倍
`os << x`	`std::ostream&`	把分佈 `x` 的參數內部狀態的文本表示寫入到 `os` 中。後：`os.fmtflags` 和填充字符 (fill character) 不變。	O(狀態大小)
`is >> u`	`std::istream&`	恢復分佈 `u` 的參數和內部狀態。前：`is` 提供之前由 `operator<<` 寫入的文本表示。後：`is.fmtflags` 不變。	O(狀態大小)

附加需求：反覆調用 x(e) 產生的序列不應因調用 os << x 而改變；用 os << x 保存，並用 is >> y 恢復到同一或另一對像 y 後，反覆調用 y(e) 產生的序列應該和原序列相同。

擬隨機數生成器 (Quasi-Random Number Generators)

一個擬隨機數生成器是一個 NumberGenerator，它根據某一算法和內部狀態提供確定的數字序列。產生的數字不具有統計學性質 (例如正態分佈或各值互相獨立)。

注意：擬隨機數生成器可以用於 Monte-Carlo 算法；在 Monte-Carlo 算法中，具有特殊性質的隨機數序列會使得估計結果較快地聚集。

[尚無模型]

Revised 05 December, 2006

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

中文版修訂：2008/1/21

在 Boost Software License, Version 1.0 的條款下發佈。(參看文件 LICENSE_1_0.txt 或在線副本 http://www.boost.org/LICENSE_1_0.txt)