伪随机数算法_伪随机数预测工具

伪随机数算法_伪随机数预测工具Random转载内容,有更改,感谢原作者(http://www.cnblogs.com/softidea/p/5824240.html#3697214)Java中的Random类生成的是伪随机数,

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Random

转载内容,有更改,感谢原作者(http://www.cnblogs.com/softidea/p/5824240.html#3697214)

Java中的Random类生成的是伪随机数,使用的是48-bit的种子,然后调用一个linear congruential formula线性同余方程(Donald Knuth的编程艺术的3.2.1节)

如果两个Random实例使用相同的种子,并且调用同样的函数,那么生成的sequence是相同的

也可以调用Math.random()生成随机数

Random实例是线程安全的,但是并发使用Random实例会影响效率,可以考虑使用ThreadLocalRandom变量。

Random实例不是安全可靠的加密,可以使用java.security.SecureRandom来提供一个可靠的加密。

Random implements Serializable 可序列化

AtomicLong seed 原子变量

解密随机数生成器(2)——从java源码看线性同余算法

上篇博客中,我们了解了基于物理现象的真随机数生成器,然而,真随机数产生速度较慢,为了实际计算需要,计算机中的随机数都是由程序算法,也就是某些公式函数生成的,只不过对于同一随机种子与函数,得到的随机数列是一定的,因此得到的随机数可预测且有周期,不能算是真正的随机数,因此称为伪随机数(Pseudo Random Number)。

 

不过,别看到伪字就瞧不起,这里面也是有学问的,看似几个简简单单的公式可能是前辈们努力了几代的成果,相关的研究可以写好几本书了!顺便提一下,亚裔唯一图灵奖得主姚期智,研究的就是伪随机数生成论(The pseudo random number generating theory)。
在这里,我重点介绍两个常用的算法:同余法(Congruential method)和梅森旋转算法(Mersenne twister)

 

1、同余法

同余法(Congruential method)是很常用的一种随机数生成方法,在很多编程语言中有应用,最明显的就是java了,java.util.Random类中用的就是同余法中的一种——线性同余法(Linear congruential method),除此之外还有乘同余法(Multiplicative congruential method)和混合同余法(Mixed congruential method)。好了,现在我们就打开java的源代码,看一看线性同余法的真面目!

 

在Eclipse中输入java.util.Random,按F3转到Random类的源代码:

 

首先,我们看到这样一段说明:

翻译过来是:

这个类的一个实现是用来生成一串伪随机数。这个类用了一个48位的种子,被线性同余公式修改用来生成随机数。(见Donald Kunth《计算机编程的艺术》第二卷,章节3.2.1)

 

显然,java的Random类使用的是线性同余法来得到随机数的。

接着往下看,我们找到了它的构造函数与几个方法,里面包含了获得48位种子的过程:

    private static final AtomicLong seedUniquifier
        = new AtomicLong(8682522807148012L);

 1 /**
 2      * Creates a new random number generator. This constructor sets
 3      * the seed of the random number generator to a value very likely
 4      * to be distinct from any other invocation of this constructor.
 5      */
 6     public Random() {
 7         this(seedUniquifier() ^ System.nanoTime());
 8     }
 9  
10     private static long seedUniquifier() {
11         // L'Ecuyer, "Tables of Linear Congruential Generators of
12         // Different Sizes and Good Lattice Structure", 1999
13         for (;;) {
14             long current = seedUniquifier.get();
15             long next = current * 181783497276652981L;
16             if (seedUniquifier.compareAndSet(current, next))
17                 return next;
18         }
19     }
20  
21     private static final AtomicLong seedUniquifier
22         = new AtomicLong(8682522807148012L);
23     public Random(long seed) {
24         if (getClass() == Random.class)
25             this.seed = new AtomicLong(initialScramble(seed));
26         else {
27             // subclass might have overriden setSeed
28             this.seed = new AtomicLong();
29             setSeed(seed);
30         }
31     }
32     private static long initialScramble(long seed) {
33         return (seed ^ multiplier) & mask;
34     }
35     。。。

 

 

复制代码
java.util.concurrent.atomic.AtomicLong
public final boolean compareAndSet(long expect,
                                   long update)
Atomically sets the value to the given updated value if the current value == the expected value.
Parameters:
expect - the expected value
update - the new value
Returns:
true if successful. False return indicates that the actual value was not equal to the expected value.
复制代码

 

这里使用了System.nanoTime()方法来得到一个纳秒级的时间量,参与48位种子的构成,然后还进行了一个很变态的运算——不断乘以181783497276652981L,这里的nanotime可以算是一个真随机数,不过有必要提的是,nanoTime和我们常用的currenttime方法不同,返回的不是从1970年1月1日到现在的时间,而是一个随机的数——只用来前后比较计算一个时间段,比如一行代码的运行时间,数据库导入的时间等,而不能用来计算今天是哪一天。

 

好了,现在我不得不佩服这位工程师的变态了:到目前为止,这个程序已经至少进行了三次随机: 

1、获得一个长整形数作为“初始种子”(系统默认的是8682522807148012L)

2、不断与一个变态的数——181783497276652981L相乘(天知道这些数是不是工程师随便滚键盘滚出来的-.-)(compare and set 保证数据的一致性)

3、与系统随机出来的nanotime值作异或运算,得到最终的种子

再往下看,就是我们常用的得到随机数的方法了,我首先找到了最常用的nextInt()函数,代码如下:

    public int nextInt() {
        return next(32);
    }

代码很简洁,直接跳到了next函数:

伪随机数算法_伪随机数预测工具
伪随机数算法_伪随机数预测工具

1     protected int next(int bits) {
2         long oldseed, nextseed;
3         AtomicLong seed = this.seed;
4         do {
5             oldseed = seed.get();
6             nextseed = (oldseed * multiplier + addend) & mask;
7         } while (!seed.compareAndSet(oldseed, nextseed));
8         return (int)(nextseed >>> (48 - bits));
9     }

View Code

 

OK,祝贺一下怎么样,因为我们已经深入到的线性同余法的核心了——没错,就是这几行代码!

在分析这段代码前,先来简要介绍一下线性同余法。

 

在程序中为了使表达式的结果小于某个值,我们常常采用取余的操作,结果是同一个除数的余数,这种方法叫同余法(Congruential method)。

线性同余法是一个很古老的随机数生成算法,它的数学形式如下:

Xn+1 = (a*Xn+c)(mod m) 

其中,

m>0,0<a<m,0<c<m

这里Xn这个序列生成一系列的随机数,X0是种子。随机数产生的质量与m,a,c三个参数的选取有很大关系。这些随机数并不是真正的随机,而是满足在某一周期内随机分布,这个周期的最长为m(一般来说是小于M的)。根据Hull-Dobell Theorem,当且仅当:

1. c和m互素;

2. a-1可被所有m的质因数整除;

3. 当m是4的整数倍,a-1也是4的整数倍时,周期为m。所以m一般都设置的很大,以延长周期。

现在我们回过头来看刚才的程序,注意这行代码:

nextseed = (oldseed * multiplier + addend) & mask;

和Xn+1=(a*Xn+c)(mod m)的形式很像有木有!

没错,就是这一行代码应用到了线性同余法公式!不过还有一个问题:怎么没见取余符号?嘿嘿,先让我们看看三个变量的数值声明:

    private static final long multiplier = 0x5DEECE66DL;
    private static final long addend = 0xBL;
    private static final long mask = (1L << 48) - 1;
 

 

其中multiplieraddend分别代表公式中的a和c,很好理解,但mask代表什么呢?其实,x & [(1L << 48)–1]与 x(mod 2^48)等价。解释如下:

x对于2的N次幂取余,由于除数是2的N次幂,如:

0001,0010,0100,1000。。。。

相当于把x的二进制形式向右移N位,此时移到小数点右侧的就是余数,如:

13 = 1101    8 = 1000

13 / 8 = 1.101,所以小数点右侧的101就是余数,化成十进制就是5

然而,无论是C语言还是java,位运算移走的数显然都一去不复返了。(什么,你说在CF寄存器中?好吧,太高端了点,其实还有更给力的方法)有什么好办法保护这些即将逝去的数据呢?

学着上面的mask,我们不妨试着把2的N次幂减一:

0000,0001,0011,0111,01111,011111。。。

怎么样,有启发了吗?

我们知道,某个数(限0和1)与1作与(&)操作,结果还是它本身;而与0作与操作结果总是0,即:

a & 1 = a,  a & 0 = 0

而我们将x对2^N取余操作希望达到的目的可以理解为:

1、所有比2^N位(包括2^N那一位)全都为0

2、所有比2^N低的位保持原样

因此, x & (2^N-1)与x(mod 2^N)运算等价,还是13与8的例子:

1101 % 1000 = 0101    1101 & 0111 = 0101

二者结果一致。

嘿嘿,讲明白了这个与运算的含义,我想上面那行代码的含义应该很明了了,就是线性同余公式的直接套用,其中a = 0x5DEECE66DL, c = 0xBL, m = 2^48,就可以得到一个48位的随机数,而且这个谨慎的工程师进行了迭代,增加结果的随机性。再把结果移位,就可以得到指定位数的随机数。

接下来我们研究一下更常用的一个函数——带参数n的nextInt:

 1     public int nextInt(int n) {
 2         if (n <= 0)
 3             throw new IllegalArgumentException("n must be positive");
 4  
 5         if ((n & -n) == n)  // i.e., n is a power of 2
 6             return (int)((n * (long)next(31)) >> 31);
 7  
 8         int bits, val;
 9         do {
10             bits = next(31);
11             val = bits % n;
12         } while (bits - val + (n-1) < 0);
13         return val;
14     }

 

显然,这里基本的思路还是一样的,先调用next函数生成一个31位的随机数(int类型的范围),再对参数n进行判断,如果n恰好为2的方幂,那么直接移位就可以得到想要的结果;如果不是2的方幂,那么就关于n取余,最终使结果在[0,n)范围内。另外,do-while语句的目的应该是防止结果为负数。

你也许会好奇为什么(n & -n) == n可以判断一个数是不是2的次方幂,其实我也是研究了一番才弄明白的,其实,这主要与补码的特性有关:

众所周知,计算机中负数使用补码储存的(不懂什么是补码的自己百度恶补),举几组例子:

2 :0000 0010      -2 :1111 1110

8 :0000 1000      -8 :1111 1000

18 :0001 0010     -18 :1110 1110

20 :0001 0100     -20 :1110 1100

不知道大家有没有注意到,补码有一个特性,就是可以对于两个相反数n与-n,有且只有最低一个为1的位数字相同且都为1,而更低的位全为0,更高的位各不相同。因此两数作按位与操作后只有一位为1,而能满足这个结果仍为n的只能是原本就只有一位是1的数,也就是恰好是2的次方幂的数了。

不过个人觉得还有一种更好的判断2的次方幂的方法:

n & (n-1) == 0

感兴趣的也可以自己研究一下^o^。

好了,线性同余法就介绍到这了,下面简要介绍一下另一种同余法——乘同余法(Multiplicative congruential method)。

上文中的线性同余法,主要用来生成整数,而某些情景下,比如科研中,常常只需要(0,1)之间的小数,这时,乘同余法是更好的选择,它的基本公式和线性同余法很像:

Xn+1=(a*Xn )(mod m )

其实只是令线性公式中的c=0而已。只不过,为了得到小数,我们多做一步:

Yn = Xn/m  

由于Xn是m的余数,所以Yn的值介于0与1之间,由此到(0,1)区间上的随机数列。

除此之外,还有混合同余法,二次同余法,三次同余法等类似的方法,公式类似,也各有优劣,在此不详细介绍了。

同余法优势在计算速度快,内存消耗少。但是,因为相邻的随机数并不独立,序列关联性较大。所以,对于随机数质量要求高的应用,特别是很多科研领域,并不适合用这种方法。

不要走开,下篇博客介绍一个更给力的算法——梅森旋转算法(Mersenne Twister),持续关注啊!

http://www.myexception.cn/program/1609435.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166746.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • android更换开机动画,修改安卓开机动画(除了部分系统 如MIUI等)

    android更换开机动画,修改安卓开机动画(除了部分系统 如MIUI等)该楼层疑似违规已被系统折叠隐藏此楼查看此楼这技术已经很久了,但还是忍不住搬运了一下。出处是百度的,很久很久以前玩手机在百度上学的我这里说的开机动画是指开机的第二屏开机动画可以在下载的rom里修改,也可以刷机后修改(推荐后者,因为比较方便,免签名)前提:手机要ROOT提权,用R.E.管理器粘贴复制首先,开机动画的地址:system\media\bootanimation.zip要修改开机动画就是修…

  • 数字证书理解(CA证书签名原理)[通俗易懂]

    数字证书理解(CA证书签名原理)[通俗易懂]目的为了防止中间人攻击和钓鱼基础概念(要求预先了解的知识概念)对称密钥体系(对称加密)和非对称密钥体系(非对称加密)都提供2份秘钥。公钥私钥是概念上的,发布出去的为公钥,留在手上的为私钥,实质上不存在公私钥区别。特殊的:在实际操作中,生成RSA(特别的:一种加密方式)密钥时会有两个秘钥,其中一份包含另一份的完整信息【此时默认命名为私钥】——->这就是为什么私钥可以推导出公…

  • Android Hook技术实践

    Android Hook技术实践一、hook简介hook俗称钩子,主要作用是替换系统内存中的对象,在上层调用此对象的方法的时候可以修改传入参数或者返回值,达到欺骗上层的目的,就像小红帽故事里的大灰狼,通过扮演小红帽的外婆的角色来达到欺骗小红帽的目的。其实hook就是一种中间人劫持的思想,如图所示:在安卓中实现hook主要通过两种方式:1.反射技术和代理实现,当然代理不管是动态还是静态的都是可以实现的,但是只能ho

  • UE4插件共享汇总大全[通俗易懂]

    UE4插件共享汇总大全[通俗易懂]UE4插件共享汇总大全:这是我发现的一个UE4插件分享网站http://ni93.com/unity/forum.php?mod=forumdisplay&fid=2列表如下,可在分享网站搜索特定名字,获取相关资源呦~~后续会持续更新这个网站的资源呦~…

  • Java学习之常用类篇

    Java学习之常用类篇0x00前言在开发中难免调用到各种api来开发程序,那就先来学习一下api的一些相关概念。0x01api的使用首先还是得来看看api的一个解释。API(Applic

    2021年12月11日
  • Python 之 pip安装 及 使用详解

    Python 之 pip安装 及 使用详解pip是啥  其实,pip就是Python标准库(ThePythonStandardLibrary)中的一个包,这个包比较特殊,用它可以来管理Python标准库(ThePythonStandardLibrary)中其他的包。pip支持从PyPI(https://pypi.org/),版本控制,本地项目以及直接从分发文件进行安装。pip是一个命令行程序。安装pip后,会向系统添加一…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号