自己动手写随机数生成函数(In C/C++)

Rainyboy

大家好，小弟刚找到组织，发现这几天咱们分区比较冷清，就把自己曾经做过的一个小东西拿出来攒攒人气，献丑了，呵呵。

出发点是想自己用C语言写一个小的工具包，实现随机数的生成，据体来说就是要实现如下两个函数接口（下面的代码同时也是rRand_2.h头文件的内容）：

1. 
   
2. #ifndef ASSUM_DEFINE_rRand_2
   
3. #define ASSUM_DEFINE_rRand_2
   
4. #define R_RAND_MAX 0xffffff
   
5. int rRand(void);//得到一个随机的整数，小于R_RAND_MAX所指定的最大值
   
6. void rRandomize(void);//初始化序列
   
7. #endif

复制代码

rRand函数的具体做法如下：
1-1，假设已经有了一个24位的二进制序列M和一个24位的任意初始值A。M[n]，A[m]表示M的第n位和A的第m位。
1-2，由运算x = M[1]*A[1] + M[2]*A[2] + ... + M[k]*A[k] + ... + M[24]*A[24];
      值得注意的是M[k]和A[k]只是一个二进制位（或者一位的二进制数）而已，其值不是0就是1，因此乘法操作就等效于于逻辑与操作了，在实际编程时可以来带便利。
1-3，将A[]序列向前移位，扔掉A[1]，即：A[k]=A[K+1],K=1,2,...,23。
1-4，将x%2的结果，即x对2的余数添加到A[]序列的最后一位：A[24]=x%2。
1-5，将新的24位A[]序列转换为十进制，作为随机数返回。
1-6，上述过程完成后，实际上初始序列A[]已经改变了，需要保留作为下一次生成随机数所用，因此，在程序中加上static修饰符。

上述操作带来了如下几个问题：
2-1，随机数的生成十分依赖于该次函数调用所使用的初始值A，而需要有一个初始化的程序使得初始值A并不是每次程序首次运行时都一样，这就是rRandomize函数的作用。
2-2，随机数的生成是由初始值A[]根据运算1-2产生的新序列，十分依赖M[]序列的性质，因为如果M[]序列全是0的话随机数序列将一直产生0，而不可能生成全部2^24-1个数字。因此M序列需要使得操作1-2产生所有可能的A[]序列，一旦找到这样的M序列，随机数的实现就与A[]序列的选取无关了。这里面涉及了很多数论的原理，我用穷举法找到了一个可用的M序列：

100000000000000001000011。

由前面的想法，程序倒是可以顺利编码，但是我们如何测试和对比rRand和库函数rand()的性能呢？

常见的测试方法有频数检验、序列检验、扑克检验、自相关检验和游程检验，对比结果如下：

检验方式	rRand() in "rRand.h"	rand() in <stdlib.h>
频数检验	[0]：13808988  49.9976% [1]：13810339  50.0024%	[0]：8297  50.644% [1]：8086  49.356%
是否通过	通过	通过
序列检验	00 _ 6904036  24.9971% 01 _ 6904951  25.0004% 10 _ 6904950  25.0004% 11 _ 6905388  25.002%	00 _ 4190  25.5753% 01 _ 4106  25.0626% 10 _ 4106  25.0626% 11 _ 3979  24.2874%
是否通过	通过	通过（个别异常）
扑克检验	00000 _ 863250  3.125% 00001 _ 863192  3.125% 00010 _ 863140  3.125% 00011 _ 862498  3.122% 00100 _ 863149  3.125% 00101 _ 863375  3.125% 00110 _ 862607  3.123% 00111 _ 862825  3.123% 01000 _ 862832  3.124% 01001 _ 863357  3.125% 01010 _ 863195  3.125% 01011 _ 863230  3.125% 01100 _ 862793  3.123% 01101 _ 863012  3.124% 01110 _ 863092  3.124% 01111 _ 863439  3.126% 10000 _ 863192  3.125% 10001 _ 862446  3.122% 10010 _ 863384  3.126% 10011 _ 862934  3.124% 10100 _ 863040  3.124% 10101 _ 863049  3.124% 10110 _ 863198  3.125% 10111 _ 863707  3.127% 11000 _ 862806  3.123% 11001 _ 862961  3.124% 11010 _ 862894  3.124% 11011 _ 863675  3.127% 11100 _ 862974  3.124% 11101 _ 863557  3.126% 11110 _ 863439  3.126% 11111 _ 863080  3.124%	00000 _ 560  3.418% 00001 _ 530  3.235% 00010 _ 523  3.192% 00011 _ 532  3.247% 00100 _ 528  3.222% 00101 _ 492  3.003% 00110 _ 525  3.204% 00111 _ 499  3.045% 01000 _ 539  3.290% 01001 _ 525  3.204% 01010 _ 528  3.222% 01011 _ 510  3.112% 01100 _ 467  2.850% 01101 _ 529  3.228% 01110 _ 525  3.204% 01111 _ 483  2.948% 10000 _ 530  3.235% 10001 _ 525  3.204% 10010 _ 497  3.033% 10011 _ 492  3.003% 10100 _ 536  3.271% 10101 _ 545  3.326% 10110 _ 471  2.874% 10111 _ 509  3.106% 11000 _ 516  3.149% 11001 _ 464  2.832% 11010 _ 553  3.375% 11011 _ 470  2.868% 11100 _ 514  3.137% 11101 _ 494  3.015% 11110 _ 483  2.948% 11111 _ 484  2.954%
是否通过	通过	通过（个别异常）
自相关检验【检验范围：0—5000】	[ 4092 ] 50.2031% [ 4093 ] 50.1407% [ 4094 ] 49.4322% [ 4095 ] 49.9878% [ 4096 ] 50.0692% [ 4097 ] 49.7558% [ 4098 ] 50.0407% …	[ 4092 ] 50.3051% [ 4093 ] 50.0407% [ 4094 ] 49.4182% [ 4095 ] 50.3418% [ 4096 ] 50.0692% [ 4097 ] 49.7558% [ 4098 ] 49.6703% …
是否通过	通过	通过
游程检验 【检验范围：1-15游程】	1 _6905609  50.0048% 2 _3452123  24.9974% 3 _1725539  12.4949% 4 _863574    6.2533% 5 _431563    3.12503% 6 _215630    1.56142% 7 _107866    0.781077% 8 _54050      0.391386% 9 _26967      0.195273% 10_13470     0.0975387% 11_ 6772      0.0490373% 12_ 3373      0.0244245% 13_ 1676      0.0121362% 14_ 850        0.006155% 15_ 418        0.00302681%	1_4164  50.7001% 2_1986  24.1812% 3_1050  12.7846% 4_493    6.00268% 5_250    3.04395% 6_133    1.61938% 7_75      0.913186% 8_28      0.340923% 9_22      0.267868% 10_7      0.0852307% 11_2      0.0243516% 12_2      0.0243516% 13_1      0.0121758% 14_0      0% 15_0      0%
是否通过	通过	不通过

可见，stdlib.h中的rand()多半是用14位位移寄存器构造出来的，而我们自己动手写的话，只要有M序列，可以将序列的长度做的足够长，已得到比库函数更好的结果。

最后，贴出rRand.cpp文件：

1. 
   
2. #include "rRand_2.h"
   
3. #include <Windows.h>
   
4. /************************************************************************/
   
5. /*按照24位M序列生成随机数的函数                                         */
   
6. /*M序列为：100000000000000001000011          */
   
7. //编码：Rainyboy 2008/3/20
   
8. //测试：Rainyboy 2008/4/27
   
9. /************************************************************************/
   
10. int rRand()
    
11. {
    
12. //参数表
    
13. static const unsigned short para_16=0x8000;
    
14. static const unsigned char para_8=0x43;
    
15. //24位寄存器
    
16. static unsigned short valu_16=0x0111;
    
17. static unsigned char valu_8=0x10;
    
18. //中间变量
    
19. unsigned short t_16;
    
20. unsigned char t_8;
    
21. //覆盖最后一位的值
    
22. int i,next_8,next_16;
    
23. //1，计算下一个位的值 next_8
    
24. t_16=para_16&valu_16;
    
25. t_8=para_8&valu_8;
    
26. next_8=0;
    
27. for(i=0;i<8;++i)
    
28. {
    
29.   if(t_8%2)
    
30.    ++next_8;
    
31.   t_8/=2;
    
32. }
    
33. for(;i<24;++i)
    
34. {
    
35.   if(t_16%2)
    
36.    ++next_8;
    
37.   t_16/=2;
    
38. }
    
39. next_8%=2;
    
40. //2，将next_8值移入valu_24的最后一位，其余位顺次左移
    
41. next_16=valu_8/0x7f;//得到第八位最高位：即将移入高16位的值
    
42. valu_8=valu_8-next_16*0x7f;
    
43. valu_8=valu_8*2+next_8;//相当于第八位左移一位，并且最低位设置成next_8
    
44. valu_16=valu_16-(valu_16/0x7fff)*0x7fff;
    
45. valu_16=valu_16*2+next_16;//同理
    
46. //3，返回valu_24的真实值
    
47. return valu_16*0x7f*2+valu_8;
    
48. }
    
49. void rRandomize(void)
    
50. {
    
51. SYSTEMTIME CurrentTime;
    
52. GetSystemTime(&CurrentTime);
    
53. int steps=CurrentTime.wSecond+CurrentTime.wMinute*60+CurrentTime.wHour*360;
    
54. for(int i=0;i<steps;++i)
    
55.   rRand();
    
56. }

复制代码

PS: 发帖子的时候这个表格把我弄得够呛……

请大家指正，共同进步！

晚睡早起

谢谢分享经验

风花雪月

不错不错，如果时间宽裕，建议楼主加入本站的管理队伍。参与本版的管理工作

Rainyboy

回复 风花雪月 的帖子

刚来没多久就去申请……怕自取其辱……

风花雪月

Rainyboy 发表于 2010-10-13 09:48

                               
登录/注册后可看大图

回复 风花雪月 的帖子

刚来没多久就去申请……怕自取其辱……

好像没有哦

Rainyboy

回复 风花雪月 的帖子

哎，尚需努力工作啊