javascript - 如何在 JavaScript 中做一个 8 位、16 位和 32 位线性反馈移位寄存器 PRNG?
问题描述
我正在寻找一个在 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
,在重新开始之前永远不会遇到重复的数字。
解决方案
这段 C 代码实现了一个 Fibonacci LFSR,看起来它是从Wikipedia中复制的,其中对其进行了更详细的描述。简而言之,它计算伪随机序列中的下一个数字,方法是将每个位向右移动lsfr >> 1
(到 2 n -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;
}
推荐阅读
- python - 从 python 内部的数据库中删除记录会出错
- vue.js - VueJS将计算值从组件传递给父级
- flutter - Flutter resizeToAvoidBottomPadding 阻塞整个屏幕
- java - 数组利率修订:
- r - r:使用 lapply 为栅格赋值
- python - cvs 文件到 host.yaml 用于 Nornir
- json - GET 参数在 URL 中起作用,但在 Postman 中不作为正文
- c# - C#项目引用之谜
- c++ - 我的 C++ 函数给出了关于声明的异常错误
- android - Android 设备未收到通过 Firebase 云消息传递发送的 5% 的推送