首页
社区
课程
招聘
[原创]计算机生成真随机数原理及实践
发表于: 2014-7-19 02:43 19692

[原创]计算机生成真随机数原理及实践

2014-7-19 02:43
19692

  经常可以听到一种痴语:计算机是有限状态机,不能产生随机数...。但实际上计算机在硬件驱动过程中是可以生成随机数的。
  首先看一个例子我们让电脑控制室内温度,工作情况大致是这样的,首先电脑要有探测温度的传感器、和控制温度的空调,电脑得到室温后和设定温度进行比较,如果温度过高则启动空调降温、过低则启动空调升温,这时室温就是以设定温度为中心的变数,从中可以提取随机数。
  我们知道电脑的显示和发声也都是属于硬件驱动,电脑通过对显卡和声卡的驱动达到显示和发声,而显卡和声卡都有自己的逻辑处理器,计算机向它们发出的指令并不是都能得到立即执行的,它们各自的处理器要根据自己的状态安排执行计算机CPU指令,所以对某些指令的执行时间是不确定的,具体表现在执行某些函数时运行时间是随机的。我们利用这种时间的不确定性就可以让计算机程序生成随机数。
  例如C++语言中的Beep(0,0),SetWindowText(NULL),MessageBeep(MB_ICONQUESTION)等,其它语言的函数也有类似情况是肯定的。
  我们只要连续调用此类函数,监测其执行时间,处理执行时间就可以达到目的。但函数的执行时间都是很短暂的,用一般测量时间的方法都太粗糙了,必须自己设计度量方法。每个计算机都有其工作频率称为主频,与之相对应的是时钟周期,做一个函数读取计算机运行以来的时钟周期,用函数运行时计算机所经历的周期数来度量时间;测量一下当前的周期数,让函数运行,再测量一下当前的周期数,两个周期数的差值再减去一个本底值就代表了函数运行时间,如此做多个循环就可以大量采集运行时间了,处理运行时间数组得到随机数组。
  且看实验数据:
  连续调用Beep(0,0)函数的运行时间115636,114283,114899,115030,114488,114350,114866,115132,114317,114757
  处理数据的方法很多这里只用最简单的方式。
  将结果放在字数组里则有  50100,48747,49363,49494,48952,48814,49330,49596,48781,49221
  放在字节数组里则有 180,107,211,86,56,174,178,188,141,69
  显然放到16位的字数组里效果不好,这是因为函数运行时间只比16位的最大值大0.7倍左右。但放到8位数组里效果不错,而其它位数的数据由此组合即可。
  通过生成大量数据的检测没有发现周期现象,也就是从不重复的,数组长度大时所有元素等概率出现随机性良好,所以它们是真随机数。在需要少量随机数的地方还是有用的,它发生简单并且不需要其它硬件。
  这里只是利用某些函数的特点来达到生成随机数的目的,因为不是专门设计制作的,所以效率不高,在主频600M的笔记本上大约达到 10k字节/s的速度。


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 3
支持
分享
最新回复 (36)
雪    币: 11096
活跃值: (17617)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
楼主思考的很深入啊,来支持
2014-7-19 09:21
0
雪    币: 144
活跃值: (43)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
mark
2014-7-19 11:45
0
雪    币: 538
活跃值: (269)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
4
楼主有没有广泛的测试过? 看看在生成大量随机数后会不会出现特殊情况(如http://www.zhihu.com/question/20222653)
2014-7-19 12:35
0
雪    币: 185
活跃值: (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
楼主根本就没理解这句“痴语”。

一、说计算机不能生成,指的是计算机通过计算不能生成。 这一点在目前是肯定的。

二、楼主你的驱动读外部数据,这明显就不是计算生成的了。  那是计算机外部的设备生成的了。
2014-7-19 13:49
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
6
这个谁不知道啊,纯计算和计算机无关,就像1+1=2一样,你还想算出3吗?
“专业路过”说的情况是有可能的,处理好就没有问题了。生成数据能通过各种测试。
2014-7-19 15:21
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
7
附件内容
1 以秒为单位用时间戳函数连续测量Beep(0,0)的数据
2 以周期数为单位连续测量Beep(0,0)的数据


上传的附件:
2014-7-20 16:09
0
雪    币: 123
活跃值: (144)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
8
#include <stdio.h>
#include <stdlib.h>

#define php_uint32 unsigned int//!!
#define php_int32 int//!!
#define PHPAPI
#define MT_N (624)
#define M             (397)                /* a period parameter */
#define N             MT_N                 /* length of state vector */
#define BG(x) (x)
#define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
#define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
#define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))
#define TSRMLS_D
php_uint32        gstate[MT_N+1] = {0};  /* state vector + 1 extra to not violate ANSI C */
php_uint32        *next = NULL;       /* next random value is computed from here */
int                        left = 0;        /* can *next++ this many times before reloading */

unsigned int asm_get_rndseed()
{
        asm("rdtsc");
}

static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state)
{
        /* Initialize generator state with seed
           See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
           In previous versions, most significant bits (MSBs) of the seed affect
           only MSBs of the state array.  Modified 9 Jan 2002 by Makoto Matsumoto. */

        register php_uint32 *s = state;
        register php_uint32 *r = state;
        register int i = 1;

        *s++ = seed & 0xffffffffU;
        for( ; i < N; ++i ) {
                *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
                r++;
        }
}

static inline void php_mt_reload()                                                         
{      
        /* Generate N new values in state
           Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */                  
        
        register php_uint32 *state = BG(gstate);                                                     
        register php_uint32 *p = state;                                                            
        register int i;                                                                             
        
        for (i = N - M; i--; ++p)
                *p = twist(p[M], p[0], p[1]);                                                      
        for (i = M; --i; ++p)
                *p = twist(p[M-N], p[0], p[1]);                                                     
        *p = twist(p[M-N], p[0], state[0]);                                                         
        BG(left) = N;
        BG(next) = state;                                                                           
}

PHPAPI php_uint32 php_mt_rand()
{
        /* Pull a 32-bit integer from the generator state
           Every other access function simply transforms the numbers extracted here */

        register php_uint32 s1;

        if (BG(left) == 0) {
                php_mt_reload();
        }
        --BG(left);

        s1 = *BG(next)++;
        s1 ^= (s1 >> 11);
        s1 ^= (s1 <<  7) & 0x9d2c5680U;
        s1 ^= (s1 << 15) & 0xefc60000U;
        return ( s1 ^ (s1 >> 18) );
}

int main()
{
        unsigned int array[1000] = {0};
        php_mt_initialize(asm_get_rndseed(), gstate);
        for (int i = 0; i < 10000000; i++)
        {
        php_mt_initialize(asm_get_rndseed(), gstate);
                unsigned int rr = php_mt_rand();
                unsigned int rr_ = rr % 1000;
                //printf("%u\n", rr_);
                array[rr_]++;
        }

        for (int i = 0; i < 1000; i++)
        {
                printf("%d:%d\n", i, array[i]);
        }
}
用这个吧,直接从php扒出来的,Mersenne Twister算法
2014-7-21 17:58
0
雪    币: 680
活跃值: (68)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
9
标记一下
2014-7-21 19:39
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
10
谢谢8楼介绍的伪随机数算法。
2014-7-21 21:47
0
雪    币: 81
活跃值: (100)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
11
就你这样2个数据根本说明不了问题,还妄想真随机,你觉得你这思路别人想不到么?为什么没有普及开呢?
2014-7-22 11:41
0
雪    币: 69
活跃值: (30)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
12
我手拿一颗球,往地上丢弹起来,每次的时间都不一样,但也不能称为随机。
2014-7-22 12:38
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
13
  是不是真随机数,要拿数据来说啦,你觉得不是你可以证明它不是,例如你可估算它后面的值,如果总是说对了,那它肯定是伪随机数了。
  楼上扔球的时间肯定是随机数了,但要将这些随机数直接使用是不行的,需要用数学方法将随机性提取出来才好作其它使用。
2014-7-22 13:10
0
雪    币: 8
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
同意你这个说法  而且我觉得lz的这个办法  虽然看出去好像是真随机   但是从科学的角度很不严谨   我不是数学专业  但是我起码了解高斯分布曲线   这东西可以反映数据分布的集中性   我觉得理想状态的随机是不可能的    就算是数学上的真随机   【我觉得】也只是对数据本身的特性规定一个指标   当这个特性达到或高于这个指标时候  我们就可以认为数据是真随机   而且  我以前看过相关的帖子   有点点印象记得数据的随机【程度】  的确是可以用某种散点图来体现的    具体可以去查阅相关资料
     第二点就是,我个人觉得lz的办法出来的数据可能会有如下情况:由于随机数的生成取决于执行时间,首先,计算机的机器时间周期不是连续且大致稳定的,函数的执行时间也肯定是机器时间周期的整数倍,毕竟函数的执行本质上就是机器指令的执行。所以我觉得这个办法出来的随机数, 从宏观来看,会在机器时间周期的整数倍那里相对集中。
    当然就像我第一点所说的,如果说从严谨的科学角度看,虽然数据是有部分集中,但是如果数据的某种特性达到某个规定真随机的指标,那么我们也是可以说办法可行,的确是真随机
2014-7-22 16:31
0
雪    币: 246
活跃值: (14)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
非常赞同!
2014-7-22 18:40
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
16
  上面是利用声卡驱动生成随机数的例子,方法很简单随便编个小程序就可以验证它,随机数根据考查是均匀分布的,是不是真随机数需要有人去证实,我还没有观察到反例。如果用来生成少量随机数还行,数量大了效率就太低了。
  上面是利用计算机硬件来获得随机数。用纯粹计算能得到真随机数吗?我想也是可以的但程序不会太简单,可以利用模拟技术来实现仅举一例,例如模拟256个小球在矩形空间做二维刚体碰撞运动,如果初速度和运动方向都是不同的,它们将演绎出形形色色的运动状态,当运动达到相对稳定后可以从小球的坐标提取随机量...

  8楼acqqer的方法也可以生成真随机数,他的方法是采用系统周期计数值作为种子,启动一个周期达到10的6000次方的随机函数取值作为输出。再优化一下是可以实用的。
2014-7-22 21:23
0
雪    币: 35
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
楼主的思路反了。不要被现象蒙蔽本质
2014-7-22 22:32
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
18
  不要总是指出不对,请用道理或数据打倒楼主的谬论。楼主认为真随机数无非是一些没有规律的乱码,即使理论上能找出规律,实际上很困难或找不出规律的都可以一样放心使用。
  有人曾对我说投掷骰子也不能生成随机数,理由是你如果把这个骰子的所有动力学参数都搞清楚,那么骰子的运动就是必然的事情毫无随机性可言,但实际上骰子的运动状态由多种因素决定,你的测量未必能在不干扰骰子运动的条件下完成,所以根本不可能实现,即使测量实现了你也无法控制那些因素,例如投掷者的力道方向等,所有那些说道毫无意义,只是搞笑而已。
2014-7-22 22:43
0
雪    币: 240
活跃值: (26)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
19
随机数貌似可以结合混沌就可以啦 ux(1-x),当u=4时,可以达到好的随机性,然后就是组装组装其他公式~
2014-7-24 00:59
0
雪    币: 204
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
不错,不错
2014-7-24 06:28
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
21
 随机函数再好也是源于同样的规则,生成的数据无法和真随机数比,尽管周期大的了不得,如果大量引用据说能产生一些不相干的东西使你的运算目标受到影响。
2014-7-24 11:12
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
jmp
22
貌似windows是多任务的,任何一个函数的执行时间可能恒定吗?
2014-7-25 01:00
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
jmp
23
http://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%95%B0
2014-7-25 01:05
0
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
24
  做过一些测试,一般函数算式等执行时间都是严格一致的。但例外的也有就像上面说的。据说有的计算机已经有专门生成随机数的芯片,但还没见到。实际上计算机的指令寄存器的数据实际是很随机的,但是无法将其读出,否则将是不错的随机数源头。
2014-7-25 10:27
0
雪    币: 3
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
不太懂这些东西,坐看打什么讨论
2014-7-25 17:25
0
游客
登录 | 注册 方可回帖
返回
//