4 个版本 (2 个重大变更)
| 0.3.0 | 2022年1月11日 |
|---|---|
| 0.2.1 | 2018年9月1日 |
| 0.2.0 | 2018年9月1日 |
| 0.1.0 | 2018年8月31日 |
#698 in 算法
每月47次 下载
26KB
228 代码行
这是什么
准随机生成器生成的值比随机数生成器生成的值分布更均匀。
随机数生成器（或近似值，例如伪随机数生成器）倾向于产生簇和间隙。例如，以下是32x32网格上由PRNG和QRNG生成的256个点
PRNG
X X X X X
X X X X X X X X X X
X X X X X
X X X X
X X X X X
X X X X X X X X
X X X X
X X X X X X X X X X
X X X X X X
X X X X X X X X
X X X X X X X X X X X
X X X X X X
X X X X X X X
X X X X X X
X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X X X
X X X X X X X
X X X X X X X X X
X X X X X X
X X X X X X X X
X X X
X X X X X X X X
X X X X X X X X X X X X X
X X X X X
X X X X X X X X X
X X X X X
X X X X X X X X
QRNG
X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X X
为什么它有用
当使用传统的PRNG时，近似算法（如数值积分和蒙特卡洛模拟）的误差曲线与1/sqrt(N)成比例，但当使用QRNG时，误差曲线与1/N成比例。
例如，以下是使用PRNG和QRNG的传统投掷飞镖蒙特卡洛π近似算法的结果。
PRNG
darts estimate error
10000000 3.14124751412 0.0003451395
20000000 3.14106475705 0.0005278965
30000000 3.14134477138 0.0002478822
40000000 3.14174547854 0.0001528250
50000000 3.14179350284 0.0002008492
60000000 3.14167225236 0.0000795988
70000000 3.14160684488 0.0000141913
80000000 3.14162498927 0.0000323357
90000000 3.14146723491 0.0001254187
100000000 3.14148591141 0.0001067422
QRNG
darts estimate error
10000000 3.14160271416 0.0000100606
20000000 3.14160175708 0.0000091035
30000000 3.14159383805 0.0000011845
40000000 3.14159457854 0.0000019250
50000000 3.14159278283 0.0000001292
60000000 3.14159245236 0.0000002012
70000000 3.14159541631 0.0000027627
80000000 3.14159453927 0.0000018857
90000000 3.14159505713 0.0000024035
100000000 3.14159319142 0.0000005378
可以看到，经过1亿次迭代后，QRNG的误差比PRNG低三个数量级。
它可以做什么
该库公开了可以生成高达32维准随机分布值的代码。只要实现了FromUniform — 一个从f64均匀分布的值构建值的特质的任何类型的数据都可以生成。
示例用法
use quasirandom::Qrng;
fn compute_pi() {
let mut qrng = Qrng::<(f64, f64)>::new(0.123);
let mut hits = 0.0;
let mut total = 0.0;
for _ in 0..1_000_000 {
let (x, y) = qrng.gen();
if x.hypot(y) < 1.0 {
hits += 1.0;
}
total += 1.0;
}
println!("pi is approximately {}", 4.0 * hits / total);
}
致谢
此生成器中使用的技巧直接取自Martin Roberts的这篇博客文章。