为什么在 Gradient Noise Generator 中从 Mersenne twister 切换到其他 PRNG 会产生不好的结果？
Why does switching from Mersenne twister to other PRNGs in Gradient Noise Generator give bad results?
我一直在尝试创建一个通用的梯度噪声生成器（它不使用散列方法来获取梯度）。代码如下：
class GradientNoise {
std::uint64_t m_seed;
std::uniform_int_distribution<std::uint8_t> distribution;
const std::array<glm::vec2, 4> vector_choice = {glm::vec2(1.0, 1.0), glm::vec2(-1.0, 1.0), glm::vec2(1.0, -1.0),
glm::vec2(-1.0, -1.0)};
public:
GradientNoise(uint64_t seed) {
m_seed = seed;
distribution = std::uniform_int_distribution<std::uint8_t>(0, 3);
}
// 0 -> 1
// just passes the value through, origionally was perlin noise activation
double nonLinearActivationFunction(double value) {
//return value * value * value * (value * (value * 6.0 - 15.0) + 10.0);
return value;
}
// 0 -> 1
//cosine interpolation
double interpolate(double a, double b, double t) {
double mu2 = (1 - cos(t * M_PI)) / 2;
return (a * (1 - mu2) + b * mu2);
}
double noise(double x, double y) {
std::mt19937_64 rng;
//first get the bottom left corner associated
// with these coordinates
int corner_x = std::floor(x);
int corner_y = std::floor(y);
// then get the respective distance from that corner
double dist_x = x - corner_x;
double dist_y = y - corner_y;
double corner_0_contrib; // bottom left
double corner_1_contrib; // top left
double corner_2_contrib; // top right
double corner_3_contrib; // bottom right
std::uint64_t s1 = ((std::uint64_t(corner_x) << 32) + std::uint64_t(corner_y) + m_seed);
std::uint64_t s2 = ((std::uint64_t(corner_x) << 32) + std::uint64_t(corner_y + 1) + m_seed);
std::uint64_t s3 = ((std::uint64_t(corner_x + 1) << 32) + std::uint64_t(corner_y + 1) + m_seed);
std::uint64_t s4 = ((std::uint64_t(corner_x + 1) << 32) + std::uint64_t(corner_y) + m_seed);
// each xy pair turns into distance vector from respective corner, corner zero is our starting corner (bottom
// left)
rng.seed(s1);
corner_0_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x, dist_y});
rng.seed(s2);
corner_1_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x, dist_y - 1});
rng.seed(s3);
corner_2_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x - 1, dist_y - 1});
rng.seed(s4);
corner_3_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x - 1, dist_y});
double u = nonLinearActivationFunction(dist_x);
double v = nonLinearActivationFunction(dist_y);
double x_bottom = interpolate(corner_0_contrib, corner_3_contrib, u);
double x_top = interpolate(corner_1_contrib, corner_2_contrib, u);
double total_xy = interpolate(x_bottom, x_top, v);
return total_xy;
}
};
然后我生成一个 OpenGL 纹理来显示，如下所示：
int width = 1024;
int height = 1024;
unsigned char *temp_texture = new unsigned char[width*height * 4];
double octaves[5] = {2,4,8,16,32};
for( int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
double d_noise = 0;
d_noise += temp_1.noise(j/octaves[0], i/octaves[0]);
d_noise += temp_1.noise(j/octaves[1], i/octaves[1]);
d_noise += temp_1.noise(j/octaves[2], i/octaves[2]);
d_noise += temp_1.noise(j/octaves[3], i/octaves[3]);
d_noise += temp_1.noise(j/octaves[4], i/octaves[4]);
d_noise/=5;
uint8_t noise = static_cast<uint8_t>(((d_noise * 128.0) + 128.0));
temp_texture[j*4 + (i * width * 4) + 0] = (noise);
temp_texture[j*4 + (i * width * 4) + 1] = (noise);
temp_texture[j*4 + (i * width * 4) + 2] = (noise);
temp_texture[j*4 + (i * width * 4) + 3] = (255);
}
}
哪个效果好：
但是 gprof 告诉我 Mersenne twister 占用了我 62.4% 的时间并且随着纹理的增加而增长。没有任何其他人会花费如此多的时间。虽然 Mersenne twister 在初始化后很快，但我每次使用它时都对其进行初始化这一事实似乎使它变得非常慢。
此初始化是 100% 必需的，以确保相同的 x 和 y 在每个整数点生成相同的梯度（因此您需要哈希函数或每次为 RNG 播种）。
我尝试将 PRNG 更改为线性同余生成器和 Xorshiftplus，虽然两者都快 运行 个数量级，但它们给出了奇怪的结果：
LCG（一次，然后运行5次才使用）
Xorshiftplus
经过一次迭代
10,000 次迭代后。
我试过：
运行 在使用输出之前生成器多次，这会导致执行缓慢或只是不同的工件。
使用初始种子后连续两次运行的输出再次为 PRNG 播种并使用 wards 后的值。结果没有区别。
这是怎么回事？我该怎么做才能更快地获得与 mersenne twister 质量相同的结果？
好的大更新：
我不知道为什么会这样，我知道这与使用的质数有关，但经过一番摸索后，似乎以下内容有效：
第1步，分别将x和y值合并为种子（并合并一些其他偏移值或附加种子值，这个数字应该是一个prime/non微不足道的因素）
第 2 步，使用这两个种子结果再次将生成器播种返回到函数中（就像 geza 所说的那样，制作的种子很糟糕）
第3步，得到结果时，不是使用取模项数(4)试图得到，或者& 3，先对结果取质数取模然后apply & 3. 我不确定素数是否是梅森素数是否重要。
这是使用 prime = 257 并使用 xorshiftplus 的结果！ （注意我用的是 2048 x 2048，其他的是 256 x 256）
你看到的是PRNG品质的实际展示。 Mersenne Twister 是性能最好的 PRNG 之一，它通过了 DIEHARD 测试。要知道生成一个随机数并不是一项简单的计算任务，因此寻求更好的性能不可避免地会导致质量不佳。 LCG 被认为是有史以来设计的最简单和最差的 PRNG，它清楚地显示了图片中的二维相关性。 Xorshift 生成器的质量在很大程度上取决于位数和参数。它们肯定比 Mersenne Twister 差，但有些 (xorshift128+) 可能工作得很好，可以通过 BigCrush 电池 TestU01 测试。
换句话说，如果您正在进行重要的物理建模数值实验，您最好继续使用 Mersenne Twister，它被认为是速度和质量之间的一个很好的权衡，它在许多标准库中都有。在不太重要的情况下，您可以尝试使用 xorshift128+ 生成器。为了获得最终结果，您需要使用加密质量的 PRNG（此处提到的 none 可用于加密目的）。
您（不知不觉地？）实现了 PRNG 非随机模式的可视化。看起来很酷！
除了 Mersenne Twister，您测试的所有 PRNG 似乎都不适合您的目的。由于我自己没有做进一步的测试，我只能建议尝试和测量更多的 PRNGs。
已知 LCG 不适合您的用途。
Xorshift128+的结果不好，因为它需要很好的播种。提供良好的播种会破坏使用它的全部目的。我不推荐这个。
但是，我建议使用整数散列。例如，来自 Bob's page.
这是该页面的第一个散列的结果，它对我来说看起来不错，而且速度很快（我认为它比 Mersenne Twister 快得多）：
这是我为生成此代码而编写的代码：
#include <cmath>
#include <stdio.h>
unsigned int hash(unsigned int a) {
a = (a ^ 61) ^ (a >> 16);
a = a + (a << 3);
a = a ^ (a >> 4);
a = a * 0x27d4eb2d;
a = a ^ (a >> 15);
return a;
}
unsigned int ivalue(int x, int y) {
return hash(y<<16|x)&0xff;
}
float smooth(float x) {
return 6*x*x*x*x*x - 15*x*x*x*x + 10*x*x*x;
}
float value(float x, float y) {
int ix = floor(x);
int iy = floor(y);
float fx = smooth(x-ix);
float fy = smooth(y-iy);
int v00 = ivalue(iy+0, ix+0);
int v01 = ivalue(iy+0, ix+1);
int v10 = ivalue(iy+1, ix+0);
int v11 = ivalue(iy+1, ix+1);
float v0 = v00*(1-fx) + v01*fx;
float v1 = v10*(1-fx) + v11*fx;
return v0*(1-fy) + v1*fy;
}
unsigned char pic[1024*1024];
int main() {
for (int y=0; y<1024; y++) {
for (int x=0; x<1024; x++) {
float v = 0;
for (int o=0; o<=9; o++) {
v += value(x/64.0f*(1<<o), y/64.0f*(1<<o))/(1<<o);
}
int r = rint(v*0.5f);
pic[y*1024+x] = r;
}
}
FILE *f = fopen("x.pnm", "wb");
fprintf(f, "P5\n1024 1024\n255\n");
fwrite(pic, 1, 1024*1024, f);
fclose(f);
}
如果您想了解哈希函数的工作原理（或者更好的是，好的哈希具有哪些属性），请查看 Bob 的页面，例如 this。
众所周知，LCG 的随机性对其参数的选择很敏感。特别是，period of a LCG 是相对于 m 参数的 - 最多 它将是 m（你的主要因素）并且对于许多值它可以更小。
同样，需要仔细选择参数才能获得 long period from Xorshift 个 PRNG。
您已经注意到一些 PRNG 提供了良好的程序生成结果，而其他则没有。为了找出原因，我会分解出 proc gen 的东西并直接检查 PRNG 输出。可视化数据的一种简单方法是构建灰度图像，其中每个像素值都是（可能缩放的）随机值。对于基于图像的东西，我发现这是找到可能导致视觉伪影的东西的简单方法。您看到的任何工件都可能导致您的 proc gen 输出出现问题。
另一种选择是尝试 Diehard tests。如果上述图像测试未能发现任何问题，我可能会使用它来确保我的 PRNG 技术值得信赖。
请注意，您的代码为 PRNG 播种，然后从 PRNG 生成一个伪随机数。您发现 xorshift128+ 中非随机性的原因是 xorshift128+ 只是将种子的两半相加（并使用结果 mod 264 作为生成的数字），然后再更改其状态（查看其 source code）。这使得 PRNG 与哈希函数有很大不同。
我一直在尝试创建一个通用的梯度噪声生成器（它不使用散列方法来获取梯度）。代码如下：
class GradientNoise {
std::uint64_t m_seed;
std::uniform_int_distribution<std::uint8_t> distribution;
const std::array<glm::vec2, 4> vector_choice = {glm::vec2(1.0, 1.0), glm::vec2(-1.0, 1.0), glm::vec2(1.0, -1.0),
glm::vec2(-1.0, -1.0)};
public:
GradientNoise(uint64_t seed) {
m_seed = seed;
distribution = std::uniform_int_distribution<std::uint8_t>(0, 3);
}
// 0 -> 1
// just passes the value through, origionally was perlin noise activation
double nonLinearActivationFunction(double value) {
//return value * value * value * (value * (value * 6.0 - 15.0) + 10.0);
return value;
}
// 0 -> 1
//cosine interpolation
double interpolate(double a, double b, double t) {
double mu2 = (1 - cos(t * M_PI)) / 2;
return (a * (1 - mu2) + b * mu2);
}
double noise(double x, double y) {
std::mt19937_64 rng;
//first get the bottom left corner associated
// with these coordinates
int corner_x = std::floor(x);
int corner_y = std::floor(y);
// then get the respective distance from that corner
double dist_x = x - corner_x;
double dist_y = y - corner_y;
double corner_0_contrib; // bottom left
double corner_1_contrib; // top left
double corner_2_contrib; // top right
double corner_3_contrib; // bottom right
std::uint64_t s1 = ((std::uint64_t(corner_x) << 32) + std::uint64_t(corner_y) + m_seed);
std::uint64_t s2 = ((std::uint64_t(corner_x) << 32) + std::uint64_t(corner_y + 1) + m_seed);
std::uint64_t s3 = ((std::uint64_t(corner_x + 1) << 32) + std::uint64_t(corner_y + 1) + m_seed);
std::uint64_t s4 = ((std::uint64_t(corner_x + 1) << 32) + std::uint64_t(corner_y) + m_seed);
// each xy pair turns into distance vector from respective corner, corner zero is our starting corner (bottom
// left)
rng.seed(s1);
corner_0_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x, dist_y});
rng.seed(s2);
corner_1_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x, dist_y - 1});
rng.seed(s3);
corner_2_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x - 1, dist_y - 1});
rng.seed(s4);
corner_3_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x - 1, dist_y});
double u = nonLinearActivationFunction(dist_x);
double v = nonLinearActivationFunction(dist_y);
double x_bottom = interpolate(corner_0_contrib, corner_3_contrib, u);
double x_top = interpolate(corner_1_contrib, corner_2_contrib, u);
double total_xy = interpolate(x_bottom, x_top, v);
return total_xy;
}
};
然后我生成一个 OpenGL 纹理来显示，如下所示：
int width = 1024;
int height = 1024;
unsigned char *temp_texture = new unsigned char[width*height * 4];
double octaves[5] = {2,4,8,16,32};
for( int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
double d_noise = 0;
d_noise += temp_1.noise(j/octaves[0], i/octaves[0]);
d_noise += temp_1.noise(j/octaves[1], i/octaves[1]);
d_noise += temp_1.noise(j/octaves[2], i/octaves[2]);
d_noise += temp_1.noise(j/octaves[3], i/octaves[3]);
d_noise += temp_1.noise(j/octaves[4], i/octaves[4]);
d_noise/=5;
uint8_t noise = static_cast<uint8_t>(((d_noise * 128.0) + 128.0));
temp_texture[j*4 + (i * width * 4) + 0] = (noise);
temp_texture[j*4 + (i * width * 4) + 1] = (noise);
temp_texture[j*4 + (i * width * 4) + 2] = (noise);
temp_texture[j*4 + (i * width * 4) + 3] = (255);
}
}
哪个效果好：
但是 gprof 告诉我 Mersenne twister 占用了我 62.4% 的时间并且随着纹理的增加而增长。没有任何其他人会花费如此多的时间。虽然 Mersenne twister 在初始化后很快，但我每次使用它时都对其进行初始化这一事实似乎使它变得非常慢。
此初始化是 100% 必需的，以确保相同的 x 和 y 在每个整数点生成相同的梯度（因此您需要哈希函数或每次为 RNG 播种）。
我尝试将 PRNG 更改为线性同余生成器和 Xorshiftplus，虽然两者都快 运行 个数量级，但它们给出了奇怪的结果：
LCG（一次，然后运行5次才使用）
Xorshiftplus
经过一次迭代
10,000 次迭代后。
我试过：
运行 在使用输出之前生成器多次，这会导致执行缓慢或只是不同的工件。
使用初始种子后连续两次运行的输出再次为 PRNG 播种并使用 wards 后的值。结果没有区别。
这是怎么回事？我该怎么做才能更快地获得与 mersenne twister 质量相同的结果？
好的大更新：
我不知道为什么会这样，我知道这与使用的质数有关，但经过一番摸索后，似乎以下内容有效：
第1步，分别将x和y值合并为种子（并合并一些其他偏移值或附加种子值，这个数字应该是一个prime/non微不足道的因素）
第 2 步，使用这两个种子结果再次将生成器播种返回到函数中（就像 geza 所说的那样，制作的种子很糟糕）
第3步，得到结果时，不是使用取模项数(4)试图得到，或者& 3，先对结果取质数取模然后apply & 3. 我不确定素数是否是梅森素数是否重要。
这是使用 prime = 257 并使用 xorshiftplus 的结果！ （注意我用的是 2048 x 2048，其他的是 256 x 256）
你看到的是PRNG品质的实际展示。 Mersenne Twister 是性能最好的 PRNG 之一，它通过了 DIEHARD 测试。要知道生成一个随机数并不是一项简单的计算任务，因此寻求更好的性能不可避免地会导致质量不佳。 LCG 被认为是有史以来设计的最简单和最差的 PRNG，它清楚地显示了图片中的二维相关性。 Xorshift 生成器的质量在很大程度上取决于位数和参数。它们肯定比 Mersenne Twister 差，但有些 (xorshift128+) 可能工作得很好，可以通过 BigCrush 电池 TestU01 测试。
换句话说，如果您正在进行重要的物理建模数值实验，您最好继续使用 Mersenne Twister，它被认为是速度和质量之间的一个很好的权衡，它在许多标准库中都有。在不太重要的情况下，您可以尝试使用 xorshift128+ 生成器。为了获得最终结果，您需要使用加密质量的 PRNG（此处提到的 none 可用于加密目的）。
您（不知不觉地？）实现了 PRNG 非随机模式的可视化。看起来很酷！
除了 Mersenne Twister，您测试的所有 PRNG 似乎都不适合您的目的。由于我自己没有做进一步的测试，我只能建议尝试和测量更多的 PRNGs。
已知 LCG 不适合您的用途。
Xorshift128+的结果不好，因为它需要很好的播种。提供良好的播种会破坏使用它的全部目的。我不推荐这个。
但是，我建议使用整数散列。例如，来自 Bob's page.
这是该页面的第一个散列的结果，它对我来说看起来不错，而且速度很快（我认为它比 Mersenne Twister 快得多）：
这是我为生成此代码而编写的代码：
#include <cmath>
#include <stdio.h>
unsigned int hash(unsigned int a) {
a = (a ^ 61) ^ (a >> 16);
a = a + (a << 3);
a = a ^ (a >> 4);
a = a * 0x27d4eb2d;
a = a ^ (a >> 15);
return a;
}
unsigned int ivalue(int x, int y) {
return hash(y<<16|x)&0xff;
}
float smooth(float x) {
return 6*x*x*x*x*x - 15*x*x*x*x + 10*x*x*x;
}
float value(float x, float y) {
int ix = floor(x);
int iy = floor(y);
float fx = smooth(x-ix);
float fy = smooth(y-iy);
int v00 = ivalue(iy+0, ix+0);
int v01 = ivalue(iy+0, ix+1);
int v10 = ivalue(iy+1, ix+0);
int v11 = ivalue(iy+1, ix+1);
float v0 = v00*(1-fx) + v01*fx;
float v1 = v10*(1-fx) + v11*fx;
return v0*(1-fy) + v1*fy;
}
unsigned char pic[1024*1024];
int main() {
for (int y=0; y<1024; y++) {
for (int x=0; x<1024; x++) {
float v = 0;
for (int o=0; o<=9; o++) {
v += value(x/64.0f*(1<<o), y/64.0f*(1<<o))/(1<<o);
}
int r = rint(v*0.5f);
pic[y*1024+x] = r;
}
}
FILE *f = fopen("x.pnm", "wb");
fprintf(f, "P5\n1024 1024\n255\n");
fwrite(pic, 1, 1024*1024, f);
fclose(f);
}
如果您想了解哈希函数的工作原理（或者更好的是，好的哈希具有哪些属性），请查看 Bob 的页面，例如 this。
众所周知，LCG 的随机性对其参数的选择很敏感。特别是，period of a LCG 是相对于 m 参数的 - 最多 它将是 m（你的主要因素）并且对于许多值它可以更小。
同样，需要仔细选择参数才能获得 long period from Xorshift 个 PRNG。
您已经注意到一些 PRNG 提供了良好的程序生成结果，而其他则没有。为了找出原因，我会分解出 proc gen 的东西并直接检查 PRNG 输出。可视化数据的一种简单方法是构建灰度图像，其中每个像素值都是（可能缩放的）随机值。对于基于图像的东西，我发现这是找到可能导致视觉伪影的东西的简单方法。您看到的任何工件都可能导致您的 proc gen 输出出现问题。
另一种选择是尝试 Diehard tests。如果上述图像测试未能发现任何问题，我可能会使用它来确保我的 PRNG 技术值得信赖。
请注意，您的代码为 PRNG 播种，然后从 PRNG 生成一个伪随机数。您发现 xorshift128+ 中非随机性的原因是 xorshift128+ 只是将种子的两半相加（并使用结果 mod 264 作为生成的数字），然后再更改其状态（查看其 source code）。这使得 PRNG 与哈希函数有很大不同。