Random

Ramdon

伪随机数

在大部分的程序语言中，随机数的生成都是伪随机的。什么是伪随机呢？伪随机性（Pseudorandomness）是指一个过程看起来是随机的，但实际上不是。它通常是使用一个确定性的算法计算出来的似乎是随机的数字，我们只要确定算法计算过程中的初始值，那么计算得到的随机数将会是固定的。

如果要获得真正的随机数，那么仅仅依靠软件去生成随机数是不够的，还需要一些随机的事件得到对应的参数指标，例如在 Linux 中获取随机数的方式就是依靠 intel CPU 电路中的热噪声信号产生的随机数，或者是用户的键盘输入的位置速度，大气中的噪声等方式获取真正的随机数，但都是依赖于专业的设备硬件。

伪随机算法

  • 线性同余方法（Linear Congruential Generator）LCG
  • 梅森旋转算法（Mersenne twister） MT
  • M-sequence（Maximum length sequence） MLS

LCG

随机数的生成采用了递归公式，这里的 $ X_n $ 表示第 n 个数，$ X_n+1 $ 表示由上一个随机数得到的当前数值，变量 a, c, m 都是常数，LCG 的周期最大为 m，但大部分情况下都会小于 m，要令 LCG 达到最大周期，需要满足以下条件：

  1. c，m 互为质数
  2. m 的所有质因数都能被整除 a - 1
  3. 如果 m 是4的倍数，那么 a - 1 也是
  4. a, c, n都比 m 小

优点：生成随机数的速度快，消耗内存小，但得知 seed 的情况下，容易根据随机的区间推断出来

MT

梅森旋转算法是基于二进制字段上的矩阵线性递归 $F_2$，对于一个 k 位的长度，MT 会在[0, $2^k$ - 1] 的区间之间生成离散型均匀分布的随机数，由于周期很长（$2^10037$ - 1）,使得随机数得区间更大，通过对 seed 生成得梅森旋转链进行旋转，处理得到旋转结果，使随机数在区间内均等分布。

因为其优秀得生成随机数速度及内存消耗空间得优化，在多个程序语言中已经使用，如 Python，PHP，Puby等。


Java Random()

Java Random() 采用得随机数生成算法是 LCS，使用了48位得种子，根据使用者得需要将最终的随机数进行移位操作，得到使用者想要的随机数。
为什么是48为的种子呢？因为 LCS 的性质导致了生成的随机数的低位并不符合随机的特点，所以需要输出更多的位状态，例如当我们需要32位的时候，就需要生成比32位更多的位，来进行移位筛选。而不选择64的原因是48位已经够用了，64位将消耗额外的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Random implements java.io.Serializable {
    // 随机数seed
    private final AtomicLong seed;

    // LCS 中的乘数 a
    private static final long multiplier = 0x5DEECE66DL;

    // LCS 中的加数 c
    private static final long addend = 0xBL;

    // LCS 中的模数 m
    private static final long mask = (1L << 48) - 1;

    // 用于计算 nextDouble 中 double 的计算单位
    private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)

    // 当使用者未指定 seed使，使用 seedUniquifier 作为初始值计算 seed
    private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);
}


Construct

构造方法主要是判断使用者是否指定 seed 的情况下，生成填充成 48位的seed，为后续的生成随机数 next() 进行种子seed 初始化操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 如果玩家没有指定 seed，那么将通过 seedUniquifier 生成一个初始的long数值
public Random() {
    // 通过 seedUniquifier() 的到一个long值，与当前时间进行异或运算
    this(seedUniquifier() ^ System.nanoTime());
}

// 默认 seedUniquifier 进行累乘计算，依赖的是系统的 CAS 操作
// 当多线程的时候，这里可能会出现耗时等待，性能损失，所以在多线程的情况下，推荐 ThreadLocalRandom
private static long seedUniquifier() {
    // L'Ecuyer, "Tables of Linear Congruential Generators of
    // Different Sizes and Good Lattice Structure", 1999
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}


// 如果有指定seed，那么将seed 进行初始化，转化成48位的seed值
public Random(long seed) {
    if (getClass() == Random.class)
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // subclass might have overriden setSeed
        this.seed = new AtomicLong();
        setSeed(seed);
    }
}

// 将初始的 seed 进行初始化，转化成指定位数
private static long initialScramble(long seed) {
    return (seed ^ multiplier) & mask;
}


next()

next() 是生成随机数的具体方法，从下面的过程中，可以看出是采用递归的方式调用 LCS, 最后生成的 48位随机数会根据取值区间 bound进行移位操作，使数值在对应区间内

1
2
3
4
5
6
7
8
9
10
11
12
13
// 具体的随机数生成过程，可对应 LCS 公式进行回顾
// 也是采用了 CAS 循环递归计算的过程
protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));

    // 最终的结果微 48位的随机数，根据取值区间进行移位取值
    return (int)(nextseed >>> (48 - bits));
}


nextInt()

因为 int 的字节长度位32位，所以在生成的随机数(48位)需要进行移位操作到32位空间，但移位的同时要注意的一个点，当使用者指定取值区间 bound的时候，因为 next() 生成随机数的区间较大，当取值区间变小后，移位的过程中，会分为多个取值空间，导致不同空间的随机数概率不同。

  • 当 n 是2的整数次幂时，n 肯定会被 $2^31$ 整除，这时候可以直接映射，只需运算一次 next(31);

  • 当 n 不是2的整数次幂，那么就会出现刚才那样分配不均匀的情况，通过 u - (r = u % bound) + m < 0 判断是否分布均匀，
    u - (r = u % bound) 表示临界点的值，由于 m = bound - 1，如果这时临界值 + m < 1，那么说明发生了溢出，那么就可以通过判断是否溢出来判断生成的随机数是否在最后一个区间，如果是的话再进行一次 next(31) 重试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int nextInt() {
    return next(32);
}

public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);

    // 获取31位的随机数
    int r = next(31);
    int m = bound - 1;

    // 判断取值区间 bound，是不是为2的整数次幂
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        r = (int)((bound * (long)r) >> 31);
    else {
        for (int u = r; u - (r = u % bound) + m < 0; u = next(31));
    }
  return r;
}


golang random

golang 中的随机数有两种一种是依靠变种的洗牌算法 math/rand，另一种是依靠操作系统的随机算法实现的真随机数 crypto/rand

发布于 
tags:
  • { Java }
  • { 源码分析 }
  • { Ramdom }