如何在 JavaScript 中实现 8 位、16 位和 32 位线性反馈移位寄存器 PRNG？

Question

我正在寻找一个在 O(1) 时间内工作并且在递增值时不会遇到重复数字的 PRNG。问题O(1) 中的唯一（非重复）随机数？没有直接得到实现的答案，而且很难看出如何应用它。据我所知，最好的答案之一是线性反馈移位寄存器。我不太明白C代码：

# include <stdint.h>
unsigned lfsr1(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    uint16_t bit;                    /* Must be 16-bit to allow bit<<15 later in the code */
    unsigned period = 0;

    do
    {   /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) /* & 1u */;
        lfsr = (lfsr >> 1) | (bit << 15);
        ++period;
    }
    while (lfsr != start_state);

    return period;
}

想知道如何将线性反馈移位寄存器 PRNG 实现为 3 个 JavaScript 函数：8 位、16 位和 32 位版本，它们作为x输入并返回一个新的x，在重新开始之前不会遇到重复的数字。

Answer 1

此 C 代码实现了斐波那契 LFSR，看起来像是从维基百科复制的，其中有更详细的描述。简而言之，它通过将每个位向右移动 ( lsfr >> 1) 来计算伪随机序列中的下一个数字，同时用选择的其他位位置的 XOR 乘积填充最高位，从而使结果序列具有最大长度（等于到 2 ⁿ \xe2\x88\x921，其中n是整数的位数）。例如，16 位 LSFR 的周期长度为 65535，并且循环遍历除零之外的每个 16 位整数值。

\n

这段代码可以很容易地翻译成 JavaScript。您只需要记住，类型的整数uint16_t仅由 16 位组成，因此任何移位到 16 位及以上的内容都将丢失。由于 Javascript 整数超过 16 位，因此在返回结果之前，您必须确保 16 位及以上的位为零。您可以通过取消& 1u表达式部分的注释来完成此操作。（忽略u；这只是告诉 C 编译器这1是一个无符号整数。）

\n

话虽如此，我不确定是否可以推荐这种 LFSR。如果计算伪随机序列中的所有值，您会发现每个值等于前一个值的一半，概率约为 50%。Xorshift算法提供了更好的数字分布，同时也易于计算。

\n

我找不到 8 位或 16 位 Xorshift 函数的任何在线资源，因此您可能需要在使用它们之前确认下面的函数实际上生成最大长度序列。

\n

function xorshift8(x) {\n    x |= x == 0;   // if x == 0, set x = 1 instead\n    x ^= (x & 0x07) << 5;\n    x ^= x >> 3;\n    x ^= (x & 0x03) << 6;\n    return x & 0xff;\n}\n\nfunction xorshift16(x) {\n    x |= x == 0;   // if x == 0, set x = 1 instead\n    x ^= (x & 0x07ff) << 5;\n    x ^= x >> 7;\n    x ^= (x & 0x0003) << 14;\n    return x & 0xffff;\n}\n\nfunction xorshift32(x) {\n    x |= x == 0;   // if x == 0, set x = 1 instead\n    x ^= (x & 0x0007ffff) << 13;\n    x ^= x >> 17;\n    x ^= (x & 0x07ffffff) << 5;\n    return x & 0xffffffff;\n}\n

\n