随机数

2021-04-17 本文已影响0人 lucasgao

[toc]

我们应用中的随机数

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

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

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

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

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

那有没有真正的随机数呢，比如我们可以再一开始生成一个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个量级。所以我们应该有个这样的结论就是随机数用我们最合适的。

随机数怎么生成的呢

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

具体的算法

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

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

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

src/math/rand/rng.go

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

一个细节

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

具体案例分析

公平的select

channel 之间的选择
1. shuffle算法
  
  如何保证公平

[生成一个字符串][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

合适的function
结合实际的mask
内存减少

随机数的定义

随机性
不可预测性
不可重现性

这三个是依次递进的，

参考资料

https://en.wikipedia.org/wiki/Pseudorandom_number_generator
随机数安全
https://blog.sqrtthree.com/articles/random-number-in-golang
https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go
https://www.zhihu.com/question/20222653

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

PHP

img

result1

Other

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

随机数