« 上一篇下一篇 »

2008-6-8 19:1:40

C语言中的随机数

今天有空看了一下C语言(以VC6为具体实现平台)中的随机数的实现,我们先看一个例子:
程序代码：[ 复制代码到剪贴板 ]
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
    int i;
    srand(time(NULL));
    for(i=0; i<RAND_MAX; i++)
    {
        printf("%d\n", rand());
    }
    return 0;
}

其中RAND_MAX是一个宏, 值等于 0x7fff, 十进制的32767,这个值是C语言中short类型的最大值. srand是初始化随机数种子(seed)的函数,是以当前时间(time(NULL))为参数, 那随机数种子是什么东西, 为什么要以当前时间为参数, 带着这些问题我们再看一个例子:
程序代码：[ 复制代码到剪贴板 ]
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int i;
    /************************************************************************/
    /* 你会发现第一行的5个数和第二行的5个数是一样的,但是他们的顺序是反的.   */
    /************************************************************************/
    printf("第一部分: \n\n");
    for(i=0; i<5; i++)
    {
        srand(i);    //种子从0递增到4
        printf("%d   ", rand());
    }
    printf("\n==========================\n");
    for(i=0; i<5; i++)
    {
        srand(4-i); //种子从4递减到0
        printf("%d   ", rand());
    }

    /************************************************************************/
    /* 你会发现第二部分的输出结果和第三部分的输出结果是一模一样             */
    /************************************************************************/

    printf("\n\n第二部分: \n");
    srand(512);
    for(i=0; i<5; i++)
    {
        printf("%d\n", rand());
    }

    printf("\n第三部分: \n");
    srand(512);
    for(i=0; i<5; i++)
    {
        printf("%d\n", rand());
    }

    printf("\n");
    return 0;
}

这个例子的输出结果如图:

按此在新窗口打开图片

由此可见, 利用不同的随机数种子产生的随机数是不同的, 而使用相同的随机数种子所产生的随机数序列都是一模一样的. 那既然是随机数,为什么产生的结果又会是一样, 带着这个疑问我们再看看VC6中随机数相关的2个标准库函数的实现:
程序代码：[ 复制代码到剪贴板 ]
#ifndef _MT
static long holdrand = 1L;
#endif  /* _MT */

void __cdecl srand (
        unsigned int seed
        )
{
#ifdef _MT /*多线程支持*/

        _getptd()->_holdrand = (unsigned long)seed;

#else  /* _MT */
        holdrand = (long)seed;
#endif  /* _MT */
}

int __cdecl rand (
        void
        )
{
#ifdef _MT /*多线程支持*/

        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L
            + 2531011L) >> 16) & 0x7fff );

#else  /* _MT */
        return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
#endif  /* _MT */
}

看了后发现原来rand 函数的实现是基于线性同余法(Linear Congruential Method, LCM) ,主要是利用了如下公式: 
Xi+1=(a*Xi+c)mod m;
其中a为乘子(常数),C为增量(常数),X0(i=0时)为种子,m为模. 
线性同余法有如下特点:
(1)0≤Xi≤m-1,即Xi只能从0,1,2,……,m-1这m个整数中取值;
(2)适当选择m,a,c,可使Xi产生循环,无论X0取何值,其循环顺序是相同的.其循环周期称为发生器周期,记为P.若P=m,则称该发生器具有满周期. 该类型的函数也被称为线性适配函数(linear congruential function).

利用这种方法可以产生一个周期比较长的各不相同的数所组成的数列,所以在一定的范围里可看成是随机数列. 但是它并不是真正的随机数, 所以一般称之为伪随机数, 可以把它理解为有规律的随机数(感觉很矛盾 ), 而控制这种规律性的最关键的要素就是随机数种子, 所以我们用当前时间做为种子,因为时间是一直在变动的. 那为什么不产生真正的随机数呢,那是因为计算机产生真正随机数方法复杂,实现麻烦,所以C语言用某种数学递推公式来产生伪随机数, 来达到与真正随机数相似的效果. 下面是一个随机数使用例子.
程序代码：[ 复制代码到剪贴板 ]
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

//产生一个区间[iStart,iEnd]上的随机浮点数
inline double RandomRange(int iStart, int iEnd)
{
    return ((double)rand()/RAND_MAX)*(iEnd-iStart) + iStart;
}

//这个函数有75%的可能性返回TRUE, 有25%的可能性返回FALSE
inline BOOL ProbabilityTest()
{
    return (rand()&3);
}

int main()
{
    int i;

    /*******************************************************/
    /* 第一部分 */
    /*******************************************************/
    srand(time(NULL));
    for (i=0; i<RAND_MAX; i++)
    {
        int iResult = rand() % 101;    //产生一个从1到100的随机数
        printf("%d\n", iResult);
    }

    /*******************************************************/
    /* 第二部分 */
    /*******************************************************/
    Sleep(1000);

       srand(time(NULL));
    for (i=0; i<RAND_MAX; i++)
    {
        double dbResult = RandomRange(5, 6); //产生一个大小介于5~6之间的浮点数
        printf("%f\n", dbResult);
    }

    /*******************************************************/
    /* 第三部分 */
    /*******************************************************/
    Sleep(1000);

       srand(time(NULL));
    int A = 0;
    int B = 0;
    for (i=0; i<RAND_MAX; i++)
    {
        if (ProbabilityTest())
        {
            A++;
            printf("有75%的可能性被执行\n");
        }
        else
        {
            B++;
            printf("有25%的可能性被执行\n");
        }
    }

    printf("A: %f   B: %f\n", (double)A/RAND_MAX, (double)B/RAND_MAX);

    return 0;
}


上面所提到的随机数生成器已经能够满足一般的需要了,但是却谈不上完美,事实上它本身还有很多缺点,首先它依赖于种子,它是利用种子计算出随机数,看了代码就知道,上一个随机数是下一个随机数的种子,本身就有很强的规律性,所以很容易遭受攻击,下面就是两起典型的案例:
一. Netscape Navigator浏览器早期版本的攻击可能是最著名的可预测随机攻击,其中用于其SSL(Secure Sockets Layer,安全套接字层)密钥的随机数有着很高的可预测性,使得SSL 失去意义.
二. 另一个就是攻击ASF软件公司的TexasHoldem Poker应用程序.这种'发牌'软件在算法中利用了Borland Delphi的随机函数.这个随机函数的实现类似于上面的rand()函数.
    正是因为它有这些缺点,所以大家把此类随机数称为伪随机数,这个'伪'字就带有'规律性'的意思. 那么到底有没有'真正的随机数'呢? 熟悉linux的人就知道,linux内核提供了一个叫/dev/random的接口,通过读取这个接口就可以获取'真正的随机数'. 那它是怎么实现的呢,在内部其实linux维护了一种称为"熵"(entropy)的东西.
那什么是"熵"? 你可以把"熵"理解成一系列的随机因子, 比如用户按键,定时器芯片的误差,空闲时间,中断时间等偶然因素. 正是利用了这些偶然的因素才能产生所谓的'真正的随机数'.  那在windows下面有没有类似的方法?当然有.  windows中提供一个API: CryptGenRandom(), 申明于Wincrypt.h. 下面是这个函数使用的一个例子:
程序代码：[ 复制代码到剪贴板 ]
#include <windows.h>
#define _WIN32_WINNT 0x0400
#include <wincrypt.h>


HCRYPTPROV hCryptProv; 

BOOL random_init()
{
    return CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, 0); 
}

ULONGLONG random()
{
    ULONGLONG uResult;
    if (!CryptGenRandom(hCryptProv, sizeof(uResult), reinterpret_cast<LPBYTE>(&uResult))) 
        return 0;
    return uResult;
}

void random_end()
{
    if(hCryptProv != NULL) CryptReleaseContext(hCryptProv, 0); 
}

int main(int argc, char* argv[])
{
    int nRetCode = 0;
    if (random_init())
    {
        for (int i=0; i<=1000; i++)
        {
            printf("%I64u\n", random());
        }
        random_end();
    }
    return 0;
}

    随机数生成本身就是一个很深奥的课题, 本文仅仅是粗略的介绍了一下,希望能对新手有所帮助. 


Tags: 计算机技术  
发布:phoneGap | 分类:技术杂谈 | 评论:0 | 浏览: