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

Question

我是 that works in O(1) time and never encounters a duplicate number as you increment through the values. The question Unique (non-repeating) random numbers in O(1)? doesn't get directly answered with an implementation, and it's hard to see how to apply it. One of the best answers as far as I can tell is the Linear-Feedback Shift Register 之一。虽然我不太明白 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 作为输入并 return 一个新的 x，在您重新开始之前永远不会遇到重复的数字。

Answer 1

此 C 代码实现了 Fibonacci LFSR，看起来它是从 Wikipedia 中复制的，其中对其进行了更详细的描述。简而言之，它通过将每一位向右移动 (lsfr >> 1) 来计算伪随机序列中的下一个数字，同时用选择的其他位位置的异或积填充最高位，这样得到的序列是最大长度（等于 2ⁿ−1，其中 n 是整数）。因此，例如，一个 16 位 LSFR 的周期长度为 65535，并循环遍历除零以外的每个 16 位整数值。

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

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

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

function xorshift8(x) {
    x |= x == 0;   // if x == 0, set x = 1 instead
    x ^= (x & 0x07) << 5;
    x ^= x >> 3;
    x ^= (x & 0x03) << 6;
    return x & 0xff;
}

function xorshift16(x) {
    x |= x == 0;   // if x == 0, set x = 1 instead
    x ^= (x & 0x07ff) << 5;
    x ^= x >> 7;
    x ^= (x & 0x0003) << 14;
    return x & 0xffff;
}

function xorshift32(x) {
    x |= x == 0;   // if x == 0, set x = 1 instead
    x ^= (x & 0x0007ffff) << 13;
    x ^= x >> 17;
    x ^= (x & 0x07ffffff) << 5;
    return x & 0xffffffff;
}

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

How to do an 8-bit, 16-bit, and 32-bit Linear-Feedback Shift Register PRNG in JavaScript?

javascript

random

cryptography

bit-manipulation