2

我正在尝试编写一些代码来创建一个伪随机整数序列，该序列使用从 0 到 n 的每个数字，然后重复。天真的方法是创建一个包含 n 个整数的数组，然后以某种方式对它们进行加扰，然后循环遍历它们。那是以空间换速度，但如果可能的话，我需要保留空间。

想到这里让我想起了“FizzleFade”，Wolfenstein 3D 使用红色填充屏幕的算法，一次一个像素，而不用两次填充同一个像素。这很简单（这个例子只打印 X 和 Y 坐标）：

    uint32_t rndval = 1;
    uint16_t x, y;
    do {
        y = rndval & 0x000FF;
        x = (rndval & 0x1FF00) >> 8;
        unsigned lsb = rndval & 1;
        rndval >>= 1;
        if (lsb) {
            rndval ^= 0x00012000;
        }
        if (x < 320 && y < 200)
            printf("x: %d y: %d\n", x, y);
    } while (rndval != 1);

至少，它看起来很简单。这似乎是一个线性反馈移位寄存器。但是，我不知道如何将此代码调整为 n 位。我不知道他们是如何确定 XOR 值的。我首先尝试将上述代码调整为 8 位值，如下所示：

#include <stdio.h>
#include <stdint.h>

int fizzlefade(void) {
    uint8_t rndval = 1;
    uint16_t values = 0;
    do {
        unsigned lsb = rndval & 1;
        rndval >>= 1;
        if (lsb) {
            rndval ^= 0x21;
        }
        printf("%d\n", rndval);
        values++;
    } while (rndval != 1);
    printf("Total number of values: %d\n", values);
    return 0;
}

int main(void) {
    printf("Fizzlefade demo\n");
    fizzlefade();
    return 0;
}

但是，无论我将 XOR 值更改为什么，我都只能得到 N 个值，其中 N < n，对于 8 位值，通常小于 100 个值。我如何确定 XOR 抽头？我需要不同的起始值吗？有比使用 LFSR 更快/更小的方法吗？

编辑：我取得了一些进展。我注意到在原始版本中，rndval 是输出值大小的两倍。所以我将我的 rndval 更改为 16 位无符号，然后将 XOR 更改为 0x1200 以模仿原始代码。这给了我 250 个随机值，都是独一无二的——非常接近！仍然不确定该怎么做。

4

1 回答 1

2

（我得跑了……但这是一个基于素数和模数的快速答案。

#include <stdio.h>
 
int main(void) {
    int max = 20;
    int prime = 29;
 
    for(int i=0; i<max; ++i)
    {
        int p_rand = (i*prime) % max + 1;
        printf("Pseudo Random: %d\n", p_rand);
    }
 
    return 0;
}

输出

Pseudo Random: 1
Pseudo Random: 10
Pseudo Random: 19
Pseudo Random: 8
Pseudo Random: 17
Pseudo Random: 6
Pseudo Random: 15
Pseudo Random: 4
Pseudo Random: 13
Pseudo Random: 2
Pseudo Random: 11
Pseudo Random: 20
Pseudo Random: 9
Pseudo Random: 18
Pseudo Random: 7
Pseudo Random: 16
Pseudo Random: 5
Pseudo Random: 14
Pseudo Random: 3
Pseudo Random: 12

（从 1 到 20 的所有数字，没有重复，以伪随机顺序排列）

于 2020-07-06T12:41:36.397 回答