自己动手写随机数生成函数(In C/C++)
本帖最后由 Rainyboy 于 2010-10-2 12:16 编辑大家好，小弟刚找到组织，发现这几天咱们分区比较冷清，就把自己曾经做过的一个小东西拿出来攒攒人气，献丑了，呵呵。
出发点是想自己用C语言写一个小的工具包，实现随机数的生成，据体来说就是要实现如下两个函数接口（下面的代码同时也是rRand_2.h头文件的内容）：
#ifndef ASSUM_DEFINE_rRand_2
#define ASSUM_DEFINE_rRand_2
#define R_RAND_MAX 0xffffff
int rRand(void);//得到一个随机的整数，小于R_RAND_MAX所指定的最大值
void rRandomize(void);//初始化序列
#endif
rRand函数的具体做法如下：
1-1，假设已经有了一个24位的二进制序列M和一个24位的任意初始值A。M，A表示M的第n位和A的第m位。
1-2，由运算x = M*A + M*A + ... + M*A + ... + M*A;
值得注意的是M和A只是一个二进制位（或者一位的二进制数）而已，其值不是0就是1，因此乘法操作就等效于于逻辑与操作了，在实际编程时可以来带便利。
1-3，将A[]序列向前移位，扔掉A，即：A=A,K=1,2,...,23。
1-4，将x%2的结果，即x对2的余数添加到A[]序列的最后一位：A=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>
频数检验：1380898849.9976%：1381033950.0024%：829750.644%：808649.356%
是否通过通过通过
序列检验00 _ 690403624.9971%01 _ 690495125.0004%10 _ 690495025.0004%11 _ 690538825.002%00 _ 419025.5753%01 _ 410625.0626%10 _ 410625.0626%11 _ 397924.2874%
是否通过通过通过（个别异常）
扑克检验00000 _ 8632503.125%00001 _ 8631923.125%00010 _ 8631403.125%00011 _ 8624983.122%00100 _ 8631493.125%00101 _ 8633753.125%00110 _ 8626073.123%00111 _ 8628253.123%01000 _ 8628323.124%01001 _ 8633573.125%01010 _ 8631953.125%01011 _ 8632303.125%01100 _ 8627933.123%01101 _ 8630123.124%01110 _ 8630923.124%01111 _ 8634393.126%10000 _ 8631923.125%10001 _ 8624463.122%10010 _ 8633843.126%10011 _ 8629343.124%10100 _ 8630403.124%10101 _ 8630493.124%10110 _ 8631983.125%10111 _ 8637073.127%11000 _ 8628063.123%11001 _ 8629613.124%11010 _ 8628943.124%11011 _ 8636753.127%11100 _ 8629743.124%11101 _ 8635573.126%11110 _ 8634393.126%11111 _ 8630803.124% 00000 _ 5603.418%00001 _ 5303.235%00010 _ 5233.192%00011 _ 5323.247%00100 _ 5283.222%00101 _ 4923.003%00110 _ 5253.204%00111 _ 4993.045%01000 _ 5393.290%01001 _ 5253.204%01010 _ 5283.222%01011 _ 5103.112%01100 _ 4672.850%01101 _ 5293.228%01110 _ 5253.204%01111 _ 4832.948%10000 _ 5303.235%10001 _ 5253.204%10010 _ 4973.033%10011 _ 4923.003%10100 _ 5363.271%10101 _ 5453.326%10110 _ 4712.874%10111 _ 5093.106%11000 _ 5163.149%11001 _ 4642.832%11010 _ 5533.375%11011 _ 4702.868%11100 _ 5143.137%11101 _ 4943.015%11110 _ 4832.948%11111 _ 4842.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 _690560950.0048%2 _345212324.9974%3 _172553912.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_416450.7001%2_198624.1812%3_105012.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文件：
#include "rRand_2.h"
#include <Windows.h>
/************************************************************************/
/*按照24位M序列生成随机数的函数 */
/*M序列为：100000000000000001000011 */
//编码：Rainyboy 2008/3/20
//测试：Rainyboy 2008/4/27
/************************************************************************/
int rRand()
{
//参数表
static const unsigned short para_16=0x8000;
static const unsigned char para_8=0x43;
//24位寄存器
static unsigned short valu_16=0x0111;
static unsigned char valu_8=0x10;
//中间变量
unsigned short t_16;
unsigned char t_8;
//覆盖最后一位的值
int i,next_8,next_16;
//1，计算下一个位的值 next_8
t_16=para_16&valu_16;
t_8=para_8&valu_8;
next_8=0;
for(i=0;i<8;++i)
{
if(t_8%2)
++next_8;
t_8/=2;
}
for(;i<24;++i)
{
if(t_16%2)
++next_8;
t_16/=2;
}
next_8%=2;
//2，将next_8值移入valu_24的最后一位，其余位顺次左移
next_16=valu_8/0x7f;//得到第八位最高位：即将移入高16位的值
valu_8=valu_8-next_16*0x7f;
valu_8=valu_8*2+next_8;//相当于第八位左移一位，并且最低位设置成next_8
valu_16=valu_16-(valu_16/0x7fff)*0x7fff;
valu_16=valu_16*2+next_16;//同理
//3，返回valu_24的真实值
return valu_16*0x7f*2+valu_8;
}
void rRandomize(void)
{
SYSTEMTIME CurrentTime;
GetSystemTime(&CurrentTime);
int steps=CurrentTime.wSecond+CurrentTime.wMinute*60+CurrentTime.wHour*360;
for(int i=0;i<steps;++i)
rRand();
}
PS: 发帖子的时候这个表格把我弄得够呛……
请大家指正，共同进步！ 谢谢分享经验 不错不错，如果时间宽裕，建议楼主加入本站的管理队伍。参与本版的管理工作 回复 风花雪月 的帖子
刚来没多久就去申请……怕自取其辱…… Rainyboy 发表于 2010-10-13 09:48 static/image/common/back.gif
回复 风花雪月 的帖子
刚来没多久就去申请……怕自取其辱……
好像没有哦{:{46}:} 回复 风花雪月 的帖子
哎，尚需努力工作啊
页:
[1]