在没有Math.Random的情况下创建随机性

2020-07-13 06:04:23

在JavaScript中,您可以使用Math.Random()创建随机数。但是,如果我们希望在没有此函数的情况下在浏览器中创建自己的随机值,该怎么办呢?

使用依赖于实现的算法或策略在该范围内随机或伪随机选择大于或等于0但小于1的正号数字值。此函数不带任何参数。

为不同领域创建的每个Math.Random函数必须从连续调用中产生不同的值序列。

下面是一个数字生成器的示例。它使用闭包来维护内部状态,并根据初始种子值创建一个数字序列。这里的种子是固定的,并且始终初始化为0。

Math.Random=(function(){let Seed=0 return function(){Seed+=1 return Seed}})()//我们可以遍历equenceMath。Random()//1数学。Random()//2Math。随机()//3。

伪随机数生成器(PRNG)以类似的方式工作。PRNG维护内部状态,并在每次请求新的随机数时对该状态应用数学。种子可以是手动的,也可以是自动的。在围棋编程语言中,您必须自己播种数学/随机。在浏览器中,Math.Random在幕后从操作系统(OS)请求随机数据作为种子。

PRNG是确定性的。相同的种子总是会产生相同的数字序列。通常,确定性的结果是首选的。例如,在所有客户端上生成相同的随机事件,而不必通过网络进行交谈。或者用于可重现的性能基准。

散列函数可用于创建PRNG。在Chrome的基准测试之一--旋转球中,我们可以看到一个这样的例子:

//v8/Benchmark/Spinging-Balls/v.js//为了使基准测试结果可预测,我们将Math.Random//替换为100%确定性替换。Math.Random=(Function(){var Seed=49734321 Return Function(){//Robert Jenkins';32位整数哈希函数。种子=种子&;0xffffff种子=(种子+0x7ed55d16+(种子<;<;12))&;0xffffff种子=(种子^0xc761c23c^(种子>;>;>;19))&;0xffffff种子=(种子+0x165667b1+(种子<;<;5))&;0xffffff。0xFFFFFF SEED=(SEED+0xfd7046c5+(SEED<;<;3)&;0xffffffff SEED=(SEED^0xb55a4f09^(SEED>;>;>;16))&;0xffffffff return(SEED&;0xfffffff)/0x10000000})()。

与我们的数字生成器一样,它在计算下一个随机数时改变其内部状态。此状态更改允许下一次呼叫生成不同的号码。

最古老和最广为人知的PRNG类型之一是线性同余发生器(LCG)。尽管它的名字有点吓人,但不需要很多代码行。

通常称为线性同余生成器(LCG),但在这种情况下,更准确地称为乘法同余生成器(MCG)或Lehmer RNG。它的状态和周期为2^31-1。它在JavaScript中非常快(可能是最快的),但是它的质量相当差。

函数lcg(A){返回函数(){a=数学。IMUL(48271,a)|0%2147483647返回(a&;2147483647)/2147483648}}。

(这是我第一次遇到Math.imul()-它提供两个参数的类似C的32位乘法。)。

在这种情况下,@bryc的评论“它的质量相当差”是什么意思?嗯,在给定某些偶数种子的情况下,当最后一步(除法)被移除时,该算法有一个模式。

//https://gist.github.com/blixt/f17b47c62508be59987b#gistcomment-2792771//@bryc://";查看不带除法的输出,并且以十六进制表示,//前几位始终相同。这在输出的//前8位中显示了一个清晰的模式:1000 000,并且它每次都会//无限地发生。这主要是由于使用偶数种子造成的。";const lcg=(S)=>;(_)=>;(s=数学。IMUL(48271,s)>;>;>;0)常量nxt=lcg(3816034944),用于(设i=0;i<;9;i++){控制台.。log(nxt()。toString(16))}/*输出:4b6c5580<;--注意最后两位数b04dc280<;--9645a58016717280d974f5805c9f22809a3a4580f196d280b5d59580*/

有很多方法可以测试随机性的质量。这些测试的一些方法和结果是外行可以理解的。其中一组顽固的测试玩了200000局掷骰子,并观察了每场比赛的胜利分布和掷出的次数。

还有一种用于LCG的测试,称为光谱测试,它将序列绘制在两个或更多个维度上。在下面的示例中,我们可以看到光谱测试测量的超平面。

PRNG最终重复其序列。在此上下文中,周期是循环重复之前的步长。更简单的PRNG,如Mulberry32,周期低至40亿,而Mersenne Twister的周期为2^19,937-1。2015年,V8团队表示,他们的Math.Random()实现使用了一种名为xorshit123+的算法,周期为2^128-1。它的介绍可以在这个差异中看到。

如果PRNG最终会重复出现,您可能会奇怪为什么我们要反复调用它。为什么不使用第一个数字,然后用新种子重置内部状态?这样做的问题是,种子需要从某个地方起源。如果我们继续要求操作系统提供更多的随机数据,则调用可能会阻塞(因为操作系统等待生成更多的随机性),并且我们的程序将会停止。

所以您已经选择了PRNG并替换了window.Math.Random。您已经将其发送给您的用户,起初,每个人似乎都很高兴。

但是等等!你忘了种子的事。现在,您的用户正在抱怨他们得到的随机数序列。每次加载客户的页面时都是一样的。他们所有的软件都是可预测的。因此,他们开发的网页游戏很容易被击败。

熵是对系统中不确定性或无序性的度量。好的熵来自周围不可预测和混乱的环境。

需要时,浏览器中安全随机数的生成由Web Cryptoography API中的Crypto.getRandomValues()执行。其由“平台特定的随机数函数、Unix/DEV/URANDOM设备、或随机或伪随机数据的其它来源”播种。

来自环境的随机性来源包括键盘间定时、来自某些中断的中断间定时以及其他事件,这些事件既是(A)非确定性的,也是(B)外部观察者难以测量的。

您可以找到许多著名的随机数生成器攻击示例,这些攻击是由于使用了错误类型(或不够)的熵而发生的。众所周知,CloudFlare使用熔岩灯作为熵源。因为我们不想创建一个安全的算法,所以像时间这样可预测的熵源就可以了。

我们可以使用Date.now()我们的种子状态。这意味着我们每毫秒都会得到一个不同的随机序列。我们还可以使用Performance.now(),它返回自时间起点以来的时间长度。

地理位置API、蓝牙API和类似产品(需要权限,在页面加载时不起作用)。

以下是Math.Random()的较慢(因为它不是本机代码)和不稳定(因为我还没有测试过它)的替代方法。还要注意,PRNG对种子状态有要求(例如,素数,128位)。我们的算法不符合Xoshio家族的SEED推荐。

//https://github.com/bryc/code/blob/master/jshash/PRNGs.md//xoshiro128+(32位格式的128位状态生成器)数学.Random=(函数xoshiro128p(){//对每个种子使用相同的值是_Screamling_error//但这对于玩具函数来说已经足够好了。让a=日期。NOW(),b=日期。NOW(),c=日期。NOW(),d=日期。NOW()RETURN函数(){让t=b<;<;9,r=a+d c=c^a d=d^b b=b^c a=a^d c=c^t d=(d<;<;11)|(d&>;>;21)return(r&>;>;>;0)/4294967296})()数学。Random()//0.5351827056147158数学。随机()//0.2675913528073579。

遗憾的是,不可能为Math.Random()创建完全符合ECMAScript的替代方法,因为该规范需要“不同的领域[从连续的调用中产生不同的值序列”。领域大致表示不同的全局环境(例如,不同的窗口或不同的WebWorker)。我们的版本不能到达它的领域之外,所以不能做出这个保证。

然而,已经有人提议使用Realms API。这样的API将提供对递增领域id之类的访问,这并不是不可想象的。这会给我们的算法带来它所需要的漏洞--访问领域--唯一的熵!

有什么意见或问题吗?我喜欢通过电子邮件与读者交谈。我写关于代码的文章。将我的帖子、项目和个人更新直接发送到您的收件箱!