Yukang's Page

关于随机数

2014-03-06

dicker

随机数代表着不确定性,其在计算机中广泛使用,比如用作加密的key、密码的生成、模拟,扑克游戏中,还有一些经典的算法(比如Monte Carlo)依赖随机数的产生。以下是一些随机数相关的问题简单总结。

随机数产生,真随机数和伪随机数生成器

随机数的产生是一个很有趣的问题。我们希望只通过计算机来产生随机数的时候会有一些困难,计算机擅长做确定的事情,按照制定的指令去依次执行。
有两种产生随机数的方法,真随机数和伪随机数,这两种有各自的优点和缺点。

伪随机数生成器(PRNG),顾名思义产生的不是严格意义上的随机数,一般是通过一些数学公式(或者计算好的表)来产生。比如简单的Linear congruential generator,可以用来产生伪随机数。伪随机数的行为是可被预测的,但是在统计意义上来说是随机的。因为这个特点其所以使用范围有限,比如一些模拟程序。而且伪随机数有可能出现固定的周期,比如下面这两幅图分别是通过真正的随机数产生器和Windows下面的PHP的伪随机数生成器产生的Bitmap,可以清楚地看到右边的那副图有规律可循。

另外如Borland随机数生成器Random的实现:

long long RandSeed = #### ;
unsigned long Random(long max)
{
long long x ;
double i ;
unsigned long final ;
x = 0xffffffff;
x += 1 ;
RandSeed *= ((long long)134775813);
RandSeed += 1 ;
RandSeed = RandSeed % x ;
i = ((double)RandSeed) / (double)0xffffffff ;
final = (long) (max * i) ;
return (unsigned long)final;
}

可以看到Random的最初一个随机数依赖于seed,后一个随机数依赖前一个随机数。

真随机数生成器(RNG),通过向计算机中引入一些不可预测的物理信息,比如键盘敲击和鼠标移动等。所以真随机数才是很难预测的或者根本来说不可预测。每个操作系统的实现有各自的区别,
比如Linux中产生随机数引入了物理噪音作为输入,比如mac地址可以用来初始化entropy pool,随机源可以加入中断时间,硬盘的寻址时间等等。
接口是/dev/random、/dev/urandom、get_random_bytes(),其中get_random_bytes在内核中使用。
/dev/random和/dev/urandom的区别是/dev/random强度更大并且是阻塞的,因为要收集更多熵。

随机数的使用

涉及到随机数的程序要特别小心。比如一个很简单的程序,我们知道C语言中的rand()产生的随机数是有范围的,0~32767,如果我要生成范围在0~10的随机数如何做?
可能你会简单认为rand()%10可以得到(惭愧我以前也这样用的),但是这真的是随机的吗?如果你把0~32767的所有数字依次%10,统计一下可以发现有的数出现的次数要大一些,因此最后出现某些数的概率相应的要大一些。

另外一个思考题,给一个rand()可以产生[1, 5]之间的随机整数,利用这个rand产生[1, 7]之间的随机整数?

另写一个抽奖程序,从30w个用户中随机抽取10w个中奖用户?

写个好的洗牌程序不容易

dicker

写一个对的洗牌程序看起来很容易,其实不然。Robert Sedgewick说过:

"That's a pretty tough thing to have happen if you're implementing online poker.
 You might want to make sure that if you're advertising that you're doing a random
 shuffle that you go ahead and do so."
  —Robert Sedgewick, Professor of Computer Science, Princeton

比如ASF Software在多年前写的一个流行的网上扑克游戏,其中的洗牌程序是这段Pascal代码:

procedure TDeck.Shuffle;
var
ctr: Byte;
tmp: Byte;
random_number: Byte;
begin
{ Fill the deck with unique cards }
for ctr := 1 to 52 do
Card[ctr] := ctr;
{ Generate a new seed based on the system clock }
randomize;
{ Randomly rearrange each card }
for ctr := 1 to 52 do begin
random_number := random(51)+1;
tmp := card[random_number];
card[random_number] := card[ctr];
card[ctr] := tmp;
end;
CurrentCard := 1;
JustShuffled := True;
end;

可以分析一下这里的好几处问题,这里的洗牌算法也有问题,52!个排列出现的概率不一样。拿三张牌来作为例子就明白了。

for (i is 1 to N)
Swap i with random position between 1 and N

dicker
可以看出231, 213, 132出现的次数要多一些,因此相对应的概率也大。

正确的洗牌程序算法是:

for (i is 1 to N)
Swap i with random position between i+1 and N

一个32位的数作为seed,对于伪随机长生器是有问题的,因为如果给定seed伪随机产生器的行为是可以预测的。
32的seed的所有可能值的个数为2^32个,这相比52!(8.0658 * 10 ^ 67)小得很多。所以对于32位的seed,甚至可以用蛮力法来攻破。

其他

摘自<<思考的乐趣>>10个人坐在一起谈天,突然他们想知道他们的平均年薪是多少,但每个人都不愿意透露自己的工资数额,有没有什么办法让他们能够得到答案,并不用担心自己的年薪被曝光?
一个简单的协议模型,当然与随机数有点关系。

参考:

Wiki: Random number generation

How We Learned to Cheat at Online Poker: A Study in Software Security

顾森, 思考的乐趣

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章