随机数

[toc]

---

我们应用中的随机数

1. 抽奖，大转盘
2. 我们经常接触的验证码
3. 密码找回
4. go中select的公平保证
5. 再然后https通信中的秘钥生成
6. 还有游戏中爆装备的概率等

你以为的随机是真的随机吗

如果我们试着在程序开始的生成一个随机数，你会发现每次都是一样的。

我们可以准确的判断出随机数是什么。

所以这也就是我们经常说的伪随机数。

那有没有真正的随机数呢，比如我们可以再一开始生成一个seed，然后再去生成随机数，这样每次都不一样了，但是这样就是真正的随机了吗。举一个极端的例子，你用随机数生成密码，种子是时间戳，而我恰好知道了你程序开始的时间，那么我就可以得到你的密码序列。

那再进一步呢，还没有别的办法，有的。我们可以根据周边物理条件来生成随机数。比如温度或者声音的变化，用户是键盘和鼠标输入等。 目前这些已经集成在部分硬件上了。

对应到我们go中呢，真随机是 crypto/rand，伪随机是math/rand，虽然真随机更好，但是我们不是需要再任何地方都用真随机的。因为有的时候安全并不重要，其次真随机性能会差很多。

// 伪随机
func Prng() int64 {
    return rand.Int63()
}

//真随机
func SecureRng() int64 {
    v, _ := srand.Int(srand.Reader, big.NewInt(math.MaxInt64))
    return v.Int64()
}

进行性能测试如下

➜  rand go test -run=none -bench=BenchmarkRng  -count=10  
goos: darwin
goarch: amd64
pkg: lucas/code/rand
BenchmarkRng/PRNG-8             79132172                14.7 ns/op
BenchmarkRng/PRNG-8             81666558                14.8 ns/op
BenchmarkRng/PRNG-8             72479173                14.8 ns/op
BenchmarkRng/PRNG-8             79032494                14.8 ns/op
BenchmarkRng/PRNG-8             75016249                15.0 ns/op
BenchmarkRng/PRNG-8             77717745                14.9 ns/op
BenchmarkRng/PRNG-8             80101124                14.8 ns/op
BenchmarkRng/PRNG-8             76762986                14.8 ns/op
BenchmarkRng/PRNG-8             77451264                14.7 ns/op
BenchmarkRng/PRNG-8             75431827                14.8 ns/op
BenchmarkRng/SRNG-8              6292308               179 ns/op
BenchmarkRng/SRNG-8              6467247               178 ns/op
BenchmarkRng/SRNG-8              6467979               178 ns/op
BenchmarkRng/SRNG-8              6464542               178 ns/op
BenchmarkRng/SRNG-8              6239452               179 ns/op
BenchmarkRng/SRNG-8              6433585               177 ns/op
BenchmarkRng/SRNG-8              6494451               178 ns/op
BenchmarkRng/SRNG-8              6401463               179 ns/op
BenchmarkRng/SRNG-8              6466090               179 ns/op
BenchmarkRng/SRNG-8              6501558               178 ns/op

可见差了1个量级。所以我们应该有个这样的结论就是随机数用我们最合适的。

随机数怎么生成的呢

<img src="http://picgo.vipkk.work/20200517013900.png" alt="image-20200517013900312" style="zoom:50%;" />

简单来说就是我们维护了一个随机数表，然后每次调用从表里取一个进行生成，然后用生成的值更新表里的值。

具体的算法

1. 线性同余法（c和java内部是这样实现的）

   <img src="http://picgo.vipkk.work/20200517014210.png" alt="image-20200517014210305" style="zoom:50%;" />

2. go的实现（继承于plan9,也没有具体的名称了）

   src/math/rand/rng.go

   /*
    * Uniform distribution
    *
    * algorithm by
    * DP Mitchell and JA Reeds
    */
   

一个细节

无论是go还是c实现上我们都需要更新内部状态，这也就是说rand生成是加锁的。

具体案例分析

1. 公平的select

   channel 之间的选择

   1. shuffle算法

      如何保证公平

2. [生成一个字符串][1]

   ➜  go test -run=none -bench=BenchmarkRandStr -benchmem
   goos: darwin
   goarch: amd64
   pkg: lucas/code/rand
   BenchmarkRandStr/str1-8                   504416              2230 ns/op             224 B/op          2 allocs/op
   BenchmarkRandStr/str2-8                   587556              1946 ns/op             224 B/op          2 allocs/op
   BenchmarkRandStr/str3-8                  1996708               583 ns/op             224 B/op          2 allocs/op
   BenchmarkRandStr/str4-8                  1859163               690 ns/op             112 B/op          1 allocs/op
   BenchmarkRandStr/str5-8                  2001969               560 ns/op             112 B/op          1 allocs/op
   PASS
   ok      lucas/code/rand 9.819s
   
   

   image-20200517022405429
   1. 合适的function
   2. 结合实际的mask
   3. 内存减少

随机数的定义

1. 随机性
2. 不可预测性
3. 不可重现性

这三个是依次递进的，

<img src="http://picgo.vipkk.work/20200517002229.png" alt="image-20200517002229634" style="zoom:50%;" />

参考资料

1. https://en.wikipedia.org/wiki/Pseudorandom_number_generator

2. 随机数安全

3. https://blog.sqrtthree.com/articles/random-number-in-golang

4. https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go

5. https://www.zhihu.com/question/20222653

6. shuffle算法

   // Shuffle pseudo-randomizes the order of elements.
   // n is the number of elements. Shuffle panics if n < 0.
   // swap swaps the elements with indexes i and j.
   func (r *Rand) Shuffle(n int, swap func(i, j int)) {
    if n < 0 {
        panic("invalid argument to Shuffle")
    }
   
    // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    // Shuffle really ought not be called with n that doesn't fit in 32 bits.
    // Not only will it take a very long time, but with 2³¹! possible permutations,
    // there's no way that any PRNG can have a big enough internal state to
    // generate even a minuscule percentage of the possible permutations.
    // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
    i := n - 1
    for ; i > 1<<31-1-1; i-- {
        j := int(r.Int63n(int64(i + 1)))
        swap(i, j)
    }
    for ; i > 0; i-- {
        j := int(r.int31n(int32(i + 1)))
        swap(i, j)
    }
   }
   

如何评价一个随机数算法的优劣

TODO

C#

<img src="http://picgo.vipkk.work/20200518133248.jpg" alt="img" style="zoom:100%;" />

PHP

img

GO

result1

Other

1. int64n 与 int64 %n 效果是不一样的