Hammersley序列的对比实现伪代码

Hammersley序列的对比实现伪代码

复制代码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序列相对来说更加地均匀，但未优化的效果也可以说是比较不错的了