Java 随机数比较和分析

上一篇 / 下一篇 2012-08-03 10:14:56 / 个人分类：Java

2s2f/Uw0e;[E0　　概况：

Q%r-}1q Z(^}Xx\s0　　本文概述2种jdk的随机数实现方式，旨在了解其运行机理。并得出运行效率比较。但这2种随机数生成还是会存在一定安全风险（伪随机数有可能会被猜出随机序列），最后还给出另一种相对更安全的随机数产生方式。附录还给出jdk的nextInt(n)函数的代码分析。

K8Ob$r"H0　　一、2种产生方式：

S$[v*EqG Yl@8J0　　一般通过jdk获取0~N（N为自然数）的随机数可以通过下面2种方式获取51Testing软件测试网N&EdCF1Cj

　　1、Math.random() ——返回[0,1)的随机小数，通过(int) （n * Math.random()）即可获取[0,n)的随机数51Testing软件测试网-~y$Io VA

5z{M.rsdM0　　2、java.util.Random的nextInt(n)方法 ——返回[0,n)的随机小数

Y4MQE8Y9y:F0　　在jdk1.6实现中，Math.random()实现如下：51Testing软件测试网4p ^4d6G^?

    public static double random() {
        if (randomNumberGenerator == null) initRNG();   // randomNumberGenerator是Math中持有的Random类单例
        return randomNumberGenerator.nextDouble();
    }

　　randomNumberGenerator 原来Math.random()还是基于Random类实现了随机数生成。

　　下面再看下Random类的nextDouble()和nextInt(n)分别怎么实现：

    public double nextDouble() {
        return (((long)(next(26)) << 27) + next(27))
     / (double)(1L << 53);
    }

    public int nextInt(int n) {
Oj%njI!Jr5\~/W\ET0        if (n <= 0)
tSq"Wp,C0            throw new IllegalArgumentException("n must be positive");51Testing软件测试网:L9P`5f)@1?g

%gHXb5F0 if ((n & -n) == n) // i.e., n is a power of 251Testing软件测试网8u,?S g4B)k
return (int)((n * (long)next(31)) >> 31);

)W1r'kmt1}K|5[0        int bits, val;
        do {
            bits = next(31);
(}} Td~-t([Ft0            val = bits % n;51Testing软件测试网k-{H-{&V
        } while (bits - val + (n-1) < 0);   // 这里为什么要这么判断，请见附录a
        return val;
}&xmnLy}%J0    }51Testing软件测试网_p(q4B`'K*lK

q'{6HJqzl`1o0　　从2段程序中可以看到，最终实现随机数的生成还是依赖于next(n)。

　　（注：next(n)的功能是产生n位bits，每个bit位随机为0或1,当n<32时，next(n)产生的随机数范围为0~2^31-1，当n=32时，产生随机数范围为-2的31次方~2^31-1。源码中的next函数最终返回return (int)(nextseed >>> (48 - bits)) 是因为随机种子是48位，所以最终返回的是随机种子的高n位bit）

'Qy;v5[5y0　　而nextDouble()中铁定调用了2次next(n)，而nextInt(n)则不确定，但平均调用next(n)的次数在2次以下（见附录b证明）。所以nextInt(n)比nextDouble()获取随机数的效率要高。

　　另外，通过(int) （n * Math.random()）获取的整数随机数其实是通过double随机数近似而来，准确性相对nextInt(n)来说应该会低些。51Testing软件测试网a1j6_\%C]#Fg

#YFq_Ct;c(@Z0　　二、下面是运行速度比较：

public class RandomTest{
static Random random = new Random();

    static int r1(int n) {
        return (int)(Math.random() * n);
    }
    static int r2(int n) {
        return random.nextInt(n);
    }

public static void main(String[] args) {
  long t1 = System.nanoTime();
  for (int i=0;i<10000;i++) {
   r1(1024);
  }
  long t2 = System.nanoTime();
  System.out.println(t2 - t1);
  t1 = System.nanoTime();
  for (int i=0;i<10000;i++) {
   r2(1024);
  }
  t2 = System.nanoTime();
  System.out.println(t2 - t1);
}
}

　　结果：51Testing软件测试网 qHZ@/e4e3F

　　3422502
"[x8SD)B0　　1335365

　　结论：无论从准确性和效率，nextInt(n)都比Math.random()要好。51Testing软件测试网v-w7puOt

'{H@aF l`0　　三、安全性

　　Random类的next(n)方法依靠确定的seed种子来计算nextseed的值（seed位48位的bit），尽管使用了各种运算，但结果仍然是线性可预测的。51Testing软件测试网 ]I2vX(z,L

C}AK'zuX@-E051Testing软件测试网j:?lfF!u,r

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
     ldseed = seed.get();
     nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

6Sxs7?n'eS0　　从程序可以看到，只要seed确定，那么nextseed也就确定，那整个序列都可以被重建出来。故如果对于随机的情景，如果攻击者获取了最初的种子seed，那么他将可以轻易模拟出随机数，并得到下一个seed。或者他通过穷举seed来获取计算的随机数来匹配程序的随机数。

;WF%t/?)H}Ap+f C0　　所以对安全性有要求的随机数应用情景，可以用java.security.SecureRandom。代替伪随机的Random类。该类继承自Random类，并覆盖了next（n）函数，所以可以利用其提供的强随机的种子算法（SHA1PRNG）来生成随机数。51Testing软件测试网m4R~(kwR!?5K

.{Klc8MTfQe0　　效率上肯定有损失，大概相差1个数量级。

51Testing软件测试网j,l,Q4nR^

    static int r3(int n) {
    final int ffset = 123456; // offset为固定值，避免被猜到种子来源（和密码学中的加salt有点类似）
     long seed = System.currentTimeMillis() + offset;
     SecureRandom secureRandom1;
  try {
   secureRandom1 = SecureRandom.getInstance("SHA1PRNG");

     secureRandom1.setSeed(seed);
     return secureRandom1.nextInt();
  } catch (NoSuchAlgorithmException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
  return 0;
    }

mocqj$l0　　四、附录

　　a、nextInt(n)函数解析

　　该函数进行的工作是把31位的原始随机范围next(31)的结果映射到[0,n)范围之内。但是，如果不经过特殊处理会出现概率不均匀。考虑下面这么一个例子，设原有均匀的随机数范围是1～100，当我要产生新的随机数范围为1～30时候，我本来可以用原随机范围产生的数分为三组，但是因为 100不被30整除，所以余下第四组是不匀称的：[1,30), [31, 60), [61, 90), [91,100),所以实际产生的结果中，产生1～10的随机数概率会比11～30的要高。jdk对这种情况的做法是，如果对31bit的随机数映射到 [0,n)的时候，如果next(31)产生的数字是最后那部分，则丢弃重试。所以nextInt(n)的循环部分就是处理这个问题。51Testing软件测试网w3Os%F'Q3H

,IhYux0　　当n是2的整数次幂时，n铁定能被2^31整除，这时候可以直接映射，进行一次next(31)运算即可。51Testing软件测试网9hw.Fyp:c/F]

Pr}"D(M&u0　　当n不是2的整数次幂是，那就会出现刚才例子中的不均匀情况。所以就要特殊处理：当bits - val + (n-1) < 0 时，判断为不均匀部分，继续循环重试。那这句判断是什么意思呢。51Testing软件测试网4_fT/u:yv&K9L

　　对于 2^31 / n = max ...val ,val是2^31除以n的余数, max是倍数，2^31-val=nMax 也就是获取不大于2^31的能整除n的最大整数。则[nMax,2^31)就是不均匀部分。如果bits落入这个范围可判为丢弃并重试。这里我们可以获得：nMax < 2^31 < n(Max+1)

　　当调用bits = next(31)时候，获取的是[0,2^31)的一个随机数，

7zTe`V0　　假如bits<nMax,则bits - val一定等于n的某个的倍数(小于Max)中，且bits-val+n-1一定小于nMax,故不需重试，直接返回结果。

"x#cMX`mM8d0}0　　假如bits>=nMax,则bits-val = nMax, 则bits-val+n-1=nMax+n-1=n(Max+1) - 1 > 2^31 -1 ,等价于若bits>=nMax,则bits-val+n-1 >= 2^31 ,由于int型2^31溢出，所以2^31<0,51Testing软件测试网%l3L Il]vi{

　　所以用while(bits-val+n-1 < 0) 来判断是否需要重试。

%Ql8X!{%XFo+U c0　　b、nextInt(n)的的循环次数为什么平均小于251Testing软件测试网2ek'af,{S |

TAj-QZe&MF0　　附录a介绍了nextInt(n)的原理，了解到产生不均匀数后需要重试。但这个重试次数是多少呢。考虑最坏情况，如nextInt(n)的 javadoc中所说，当n=2^30+1时，最糟糕，[nMax,2^31)的范围达到最大。要使因为如果n<2^30+1更小，那么一定能找到 newMax使得[nNewMax, 2^31) 的范围更小。

　　当n=2^30+1,则不均匀范围[2^30+1, 2^31)和均匀范围[0, 2^30)的数目基本是一样的，所以这个时候有50%的机会要重试。即最坏情况下也只有50%的概率重试。

Rf:[8Ji0　　所以总体上来说nextInt(n)的平均调用next(n)次数小于2，这也是为什么比Math.random()要快的原因。

收藏举报

TAG:

查看全部评论

bob123654

不要让那些真正对你好的人，慢慢的从你的生活中消失，无论爱情还是友情，都需要用心经营。

Java 随机数比较和分析

用户菜单

我的栏目

标题搜索

日历

我的存档

数据统计

RSS订阅