如何量化僞隨機數發生器的質量？

Question

這是基於this question。提出了許多答案，它們會產生非均勻分佈，我開始想知道如何量化產出的不均勻性。我不是在尋找模式問題，只是單一的價值方面。

什麼是公認的程序？

---

我的當前的想法是每計算機呼叫的平均Shannon entropy通過計算每個值的熵和服用的加權平均。這可以被調整到預期的價值。

我的擔憂是

1. 這是正確的？
2. 如何在不失去精度的情況下計算這些值？

對於＃1我想知道我是否正確。

對於＃2，我擔心的是我會處理大小類似1/7 +/- 1e-18的數字，我擔心浮點錯誤會殺死我，除了最小的問題。計算的確切形式可能會導致一些重大差異，我似乎回想起一些特殊日誌情況下有一些ASM選項，但我似乎無法找到關於此的文檔。

---

在這種情況下使用是需要一個「好」爲PRNG範圍[1,n]，併爲範圍[1,m]一個SRNG。問題是結果比輸入差多少？

我有什麼是預計每個輸出值的發生率。

Answer 1

NIST有一套文檔和工具，用於統計分析隨機數生成器跨越各種指標。

http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

許多這些測試也併入Dieharder PRNG測試套件。

http://www.phy.duke.edu/~rgb/General/rand_rate.php

有一噸不同的指標，因爲有使用的PRNG很多很多不同的方式。你不能在真空中分析PRNG - 你必須瞭解用例。這些工具和文檔提供了大量的信息來幫助您，但是在一天結束之前，您仍然必須瞭解實際需要的內容，然後才能確定算法是否合適。 NIST的文檔是全面的，如果有點密集。

- 亞當

Answer 2

This page討論檢查，如果你得到一個壞分配的一種方式：在現場繪製的僞隨機值，然後只是看着他們。

Answer 3

TestU01比Dieharder擁有更嚴格的測試集。最大的測試集稱爲「BigCrush」，但執行需要很長時間，所以也有稱爲「Crush」和「SmallCrush」的子集。這個想法是第一次嘗試SmallCrush，如果PRNG通過，嘗試粉碎，如果它通過，BigCrush。如果它也通過了，它應該足夠好。

您可以獲得TestU01 here。