自己写的一个C++高位长真/伪随机数发生器类

59 阅读 0 评论 39 点赞

我是靠谱客的博主专注枫叶，最近开发中收集的这篇文章主要介绍自己写的一个C++高位长真/伪随机数发生器类，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

　　一直想要弄一个能够生成真随机数的类，但因未能找到合适的真随机因子而未能完成。前些天偶然了解到IA32的CPU具有一个时钟周期计数器，能够提供自CPU复位后至今累计的时钟周期数。忽然觉得这个正是最易得到而又最难预测的真随机因子。

　　这里我们不讨论严格意义上的“真随机”数，以免陷入无尽的口水里。我认为由于系统运行状况的不确定性，实际上连总是以固定间隔获取时钟计数都很难做到。再加上多核处理器各核心的负载变化、睿频功能的状态变更、CPU流水线被中断的情况不同、CPU缓存的命中变化、操作系统的任务调度、真正随机的外界事件干扰(比如键盘/鼠标操作，网络通信变化等等)......如此多的变数影响下，我们获得的时钟计数完全无法预测。用它做真随机因子的随机数算法就已经是真正的随机数了。至少，对于日常的需求而言已经可以得到满足了。

　　和通常使用的系统时间毫秒数相比较，这个时钟周期计数更为多变。系统时间一毫秒才改变一次，足够一个快速的随机数发生器产生超过十万个随机数了。因为期间系统时间没有改变，用它生成的随机数其实还是一个固定序列。而时钟计数则能保证每次调用都不相同，生成一个随机数的时间至少要经过几十个时钟周期了。使用它来生成随机数能保证不会出现固定序列的现象。

　　另一个好处是运行效率很高。系统时间的获取需要调用操作系统API，费时费力。而时钟计数则仅需几条汇编命令就能取到，轻巧容易。

　　网上曾有人直接把时钟周期计数的低位作为随机数来使用，但我认为这还是不妥。毕竟该数字重复一次的周期太长了点，在此期间用户获得的就是一个虽然间距随机但却一直在不断增大的数字序列，怎么看都不像是一个随机数。所以，我把他作为随机因子添加到线性同余法随机数发生器的算法里，使得到的数字序列成为真正无规律的真随机序列。

　　这个算法的运行效率还是非常高的，不带参数时大约能在几纳秒的时间里生成一个真随机数。带上参数后63位算法的速度下降很多，大约需要15纳秒才能生成一个。原因是它需要做128位乘法运算来整理返回值。我最初用浮点数来做返回值整理，速度更快，但发现计算误差太可恶了：用n做参数本该生成0到n-1的数值，结果调试中改置极限参数后竟然在输出里看到了n。于是改用内联汇编来做整理运算。

//  RandomDigit.h

//  定义了一个高速真/伪随机数类，可用以快速生成随机数
//  伪随机数可通过设置种子来生成特定序列
//  真随机数没有固定序列，每次生成都随机器状态而改变，无法预测

class RandomDigit
{
private:
    static int seed;
    static long long seedH;
    static unsigned int arrange(unsigned int n);        //  整理函数，用于将随机数整理成指定范围的整数
    static unsigned long long arrange(unsigned long long n);    //  高精度重载型式

public:
    static void SetSeed(long long seed);                //  设置随机数种子

    static int Random();                                //  获取31位随机数
    static unsigned int Random(unsigned int n);         //  获取自0~n-1之间的一个随机整数
    static long long RandomHight();                     //  获取63位随机数
    static unsigned long long RandomHight(unsigned long long n);    //  获取自0~n-1之间的一个随机整数

    static int RealRandom();                            //  获取31位真随机数
    static unsigned int RealRandom(unsigned int n);     //  获取0~n-1之间的一个真随机整数
    static long long RealRandomHight();                 //  获取63位真随机数
    static unsigned long long RealRandomHight(unsigned long long n);//  获取0~n-1之间的一个真随机整数
};

//  RandomDigit.cpp

#include "RandomDigit.h"

int RandomDigit::seed;
long long RandomDigit::seedH;

void RandomDigit::SetSeed(long long seed)
{
    seed=seedH=seed;
}

int RandomDigit::Random()
{
    return seed=((seed<<16)+seed+0x1db3d743)&0x7fffffff;
}

unsigned int RandomDigit::Random(unsigned int n)
{
    Random();
    return arrange(n);
}

long long RandomDigit::RandomHight()
{
    return seedH=((seedH<<32)+seedH+0xdb3d742c265539d)&0x7fffffffffffffff;
}

unsigned long long RandomDigit::RandomHight(unsigned long long n)
{
    RandomDigit::RandomHight();
    return arrange(n);
}

int RandomDigit::RealRandom()
{
    __asm
    {
        rdtsc
        add eax,RandomDigit::seed
        and eax,0x7fffffff
        mov RandomDigit::seed,eax
    }
    return Random();
}

unsigned int RandomDigit::RealRandom(unsigned int n)
{
    RandomDigit::RealRandom();
    return arrange(n);
}

long long RandomDigit::RealRandomHight()
{
    __asm
    {
        rdtsc
        add dword ptr [RandomDigit::seedH],eax
        adc eax,dword ptr [RandomDigit::seedH+4]
        and eax,0x7fffffff
        mov dword ptr [RandomDigit::seedH+4],eax
    }
    return RandomHight();
}

unsigned long long RandomDigit::RealRandomHight(unsigned long long n)
{
    RandomDigit::RealRandomHight();
    return arrange(n);
}

unsigned int RandomDigit::arrange(unsigned int n)
{
    return (unsigned int)(((unsigned long long)seed*(unsigned long long)n)>>31);
}

unsigned long long RandomDigit::arrange(unsigned long long n)
{
        //  浮点计算不安全，只好用汇编来加速了。
    unsigned long long product;

        __asm                           //  实现128位乘法( seedH * n )，并将结果右移63位后存入product中。
    {
        mov eax,dword ptr [seedH]
        mul dword ptr [n]
        mov ebx,edx
        mov eax,dword ptr [seedH+4]
        mul dword ptr [n]
        add ebx,eax
        xor ecx,ecx
        adc ecx,edx
        xor edx,edx
        mov eax,dword ptr [n+4]
        cmp eax,edx
        jz zero
        mul dword ptr [seedH]
        add ebx,eax
        adc ecx,edx
        mov eax,dword ptr [n+4]
        jc cseted
        mul dword ptr [seedH+4]
        jmp continuation
cseted:
        mul dword ptr [n+4]
        inc edx
continuation:
        add ecx,eax
        xor eax,eax
        adc edx,eax
zero:
        shl ebx,1
        rcl ecx,1
        rcl edx,1
        mov dword ptr [product],ecx
        mov dword ptr [product+4],edx
    }

    return product;
}