Hammersley序列的对比实现伪代码
代码语言：javascript复制复制代码12345678910111213141516171819202122CPPdouble make_halton_sequence(int index, int base) {
double f = 1, r = 0;
while (index > 0) {
f = f / base;
r = r f * (index % base);
index = index / base;
}
return r * randpoint_scale;
}
void halton_random()
{
// 此处讨论生成二维随机数，如要产生多维，base需要是不重复的质数即可
// 三维:base 2 3 5
for (uint i = 0u; i < max_num; i)
{
draw_points.emplace_back(make_halton_sequence(i, 2), make_halton_sequence(i, 3));
// 三维
draw_points.emplace_back(make_halton_sequence(i, 2), make_halton_sequence(i, 3)
, make_halton_sequence(i, 5));
}
}Halton序列在底数较大的时候，样本个数会有很严重的correlation。所以需要采用Scrambling解决这个问题RadicalInverse的实现的效率依赖于一个循环，将索引Index的数字左右颠倒。这一步骤可以通过一次将多个连续数字的左右颠倒连同Faure Scrambling预计算出来，存在一个查找表里。运行的时候直接将索引的多个数字提取出来，然后直接查表得到结果。下面给出一段以5作为底数的Halton序列实现 详细做法可参考：HALTON The Halton Quasi Monte Carlo (QMC) Sequence
与Hammersley序列的对比
Hammersley序列的介绍与实现可参考这篇：
- 低差异序列 (low-discrepancy sequences)之Hammerysley在半球中采样点方法的介绍
Halton序列无需在生成随机数之前，知道需要生成随机点的个数，但是在用一些比较大的质数作为底数时，Halton序列的分布在点的数量不那么多的时候并不会均匀的分布，只有当点的数量接近底数的幂的时候分布才会逐渐均匀
效果对比
Halton序列比一般的伪随机数更加地分布均匀，因为此处是没有对Halton进行优化的，即没有Scrambling，可从另一幅图看到，Hammersley序列比未优化的Halton序列相对来说更加地均匀，但未优化的效果也可以说是比较不错的了
