使用 srand() 随机游走出现蝴蝶图案，为什么？

Question

大约 3 年前，我和同事一起用 C++ 编写了一个 2D 随机游走程序，起初它似乎工作正常，因为我们每次都获得了不同的模式。但是，每当我们决定将步数增加到某个阈值以上时，就会出现一个明显的蝴蝶图案，我们注意到代码的每个运行都会重复该图案，但从蝴蝶的不同位置开始。我们当时总结报告说是srand()函数关联的伪随机数生成器的问题，今天又找到了这个报告，还有一些想了解的地方。我想更好地理解伪随机生成器是如何工作的，以获得这种对称性和 ciclic 模式。我正在谈论的模式是这样的（这些步骤以彩虹序列进行颜色编码以评估步行的进展）：

编辑：

我正在添加用于获取此图的代码：

#include<iostream>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include <fstream>
#include <string.h>
#include <string>
#include <iomanip>

using namespace std;

int main ()
{
srand(time(NULL));
int num1,n=250000;



ofstream rnd_coordinates("Random2D.txt");
float x=0,y=0,sumx_f=0,sumy_f=0,sum_d=0,d_m,X,t,d;
float x_m,y_m;

x=0;
y=0;

for(int i=0;i<n;i++){

    t=i;
    num1= rand()%4;

    if(num1==0){
        x++;
    }
    if(num1==1){
        x--;
    }
    if(num1==2){
        y++;
    }
    if(num1==3){
        y--;
    }

    rnd_coordinates<<x<<','<<y<<','<<t<<endl;

}

rnd_coordinates.close();


return 0;
}

Answer 1

每个伪随机数发生器都是一些数字序列的循环。我们区分 "good" prngs 和 "bad" prngs 的方法之一是这个序列的长度。有一些状态与生成器相关联，因此最大周期受有多少不同状态的限制。

您的实现有一个 "short" 周期，因为它在小于宇宙年龄的时间内重复。它可能有 32 位状态，所以周期最多 2^32.

由于您使用的是 C++，您可以使用随机种子再试一次 std::mt19937，您将不会看到重复。

Answer 2

您永远不会达到 rand() 的周期，但请记住，您实际上并没有使用整个 rand() 范围，它完全保证了 2^32 周期。

考虑到这一点，您有 2 个选择：

使用所有位。 rand() returns 2 个字节（16 位），您需要 2 位（用于 4 个可能的值）。将 16 位输出拆分为 2 位块并按顺序使用它们。
至少，如果您坚持使用惰性 %n 方式，请选择一个不是周期除数的模数。例如选择 5 而不是 4，因为 5 是素数，如果你得到第 5 个值，则重新掷骰。

Answer 3

您可能想看看我对另一个关于旧 rand() 实现的问题的回答。有时，对于旧的 rand() and srand() 函数，低阶位的随机性远低于高阶位。其中一些较旧的实现仍然存在，您可能使用过一个。

Answer 4

下面的代码构成了一个完整的可编译示例。

您的问题是从随机生成器中删除位。让我们看看如何编写一个不丢位的随机位对源。它要求 RAND_MAX 的形式为 2^n−1，但这个想法可以扩展到支持任何 RAND_MAX >= 3.

#include <cassert>
#include <cstdint>
#include <cstdlib>

class RandomBitSource {
    int64_t bits = rand();
    int64_t bitMask = RAND_MAX;
    static_assert((int64_t(RAND_MAX + 1) & RAND_MAX) == 0, "No support for RAND_MAX != 2^(n-1)");
public:
    auto get2Bits() {
        if (!bitMask) // got 0 bits
            bits = rand(), bitMask = RAND_MAX;
        else if (bitMask == 1) // got 1 bit
            bits = (bits * (RAND_MAX+1)) | rand(), bitMask = (RAND_MAX+1) | RAND_MAX;

        assert(bitMask & 3);
        bitMask >>= 2;
        int result = bits & 3;
        bits >>= 2;
        return result;
    }
};

那么，随机游走的实现可以如下所示。请注意，' 数字分隔符是一个 C++14 功能 - 非常方便。

#include <vector>

using num_t = int;
struct Coord { num_t x, y; };

struct Walk {
    std::vector<Coord> points;
    num_t min_x = {}, max_x = {}, min_y = {}, max_y = {};
    Walk(size_t n) : points(n) {}
};

auto makeWalk(size_t n = 250'000)
{
    Walk walk { n };
    RandomBitSource src;
    num_t x = 0, y = 0;

    for (auto& point : walk.points)
    {
        const int bits = src.get2Bits(), b0 = bits & 1, b1 = bits >> 1;
        x = x + (((~b0 & ~b1) & 1) - ((b0 & ~b1) & 1));
        y = y + (((~b0 & b1) & 1) - ((b0 & b1) & 1));

        if (x < walk.min_x)
            walk.min_x = x;
        else if (x > walk.max_x)
            walk.max_x = x;
        if (y < walk.min_y)
            walk.min_y = y;
        else if (y > walk.max_y)
            walk.max_y = y;

        point = { x, y };
    }
    return walk;
}

稍加努力，我们就可以将它变成一个交互式 Qt 应用程序。按 Return 生成一个新图像。

图像以显示它的屏幕的原始分辨率查看，即它映射到物理设备像素。图像未缩放。相反，它会在需要时旋转以更好地适应屏幕的方向（纵向与横向）。这是给肖像监视器爱好者的:)

#include <QtWidgets>

QImage renderWalk(const Walk& walk, Qt::ScreenOrientation orient)
{
    using std::swap;
    auto width = walk.max_x - walk.min_x + 3;
    auto height = walk.max_y - walk.min_y + 3;
    bool const rotated = (width < height) == (orient == Qt::LandscapeOrientation);
    if (rotated) swap(width, height);
    QImage image(width, height, QPixmap(1, 1).toImage().format());
    image.fill(Qt::black);

    QPainter p(&image);
    if (rotated) {
        p.translate(width, 0);
        p.rotate(90);
    }
    p.translate(-walk.min_x, -walk.min_y);

    auto constexpr hueStep = 1.0/720.0;
    qreal hue = 0;
    int const huePeriod = walk.points.size() * hueStep;
    int i = 0;
    for (auto& point : walk.points) {
        if (!i--) {
            p.setPen(QColor::fromHsvF(hue, 1.0, 1.0, 0.5));
            hue += hueStep;
            i = huePeriod;
        }
        p.drawPoint(point.x, point.y);
    }
    return image;
}

#include <ctime>

int main(int argc, char* argv[])
{
    srand(time(NULL));
    QApplication a(argc, argv);
    QLabel view;
    view.setAlignment(Qt::AlignCenter);
    view.setStyleSheet("QLabel {background-color: black;}");
    view.show();

    auto const refresh = [&view] {
        auto *screen = view.screen();
        auto orientation = screen->orientation();
        auto pixmap = QPixmap::fromImage(renderWalk(makeWalk(), orientation));
        pixmap.setDevicePixelRatio(screen->devicePixelRatio());
        view.setPixmap(pixmap);
        view.resize(view.size().expandedTo(pixmap.size()));
    };
    refresh();
    QShortcut enter(Qt::Key_Return, &view);
    enter.setContext(Qt::ApplicationShortcut);
    QObject::connect(&enter, &QShortcut::activated, &view, refresh);
    return a.exec();
}

使用 srand() 随机游走出现蝴蝶图案，为什么？

Butterfly pattern appears in random walk using srand(), why?

c++

random

srand

random-walk

random-seed