论坛 › 算法交流 › 求随机产生0-2^32-1内整数算法

无心人 发表于 2008-3-17 09:12:46

求随机产生0-2^32-1内整数算法

要求速度快
且满足概率意义上的平均分布
即假设产生100万数据
如果平均切分区间为10份
则每个区间的数字个数都要接近10万
总偏差不能超过10%

同样道理， 做其他等分切分
则区间分布偏差也要小

gxqcn 发表于 2008-3-17 09:36:08

关于伪随机数的生成，学问很深。

可参考 Donald E. Knuth 的 The Art Of Computer Programming (volume2)，即mathe女儿常翻的那本:)
在这本书里有一段代码，其随机性比较好，上限虽没有楼主要求的那么大，
但也达到了(230-1)，比标准C中的 rand() 函数（上限仅(215-1)）好了不少。

无心人 发表于 2008-3-17 09:46:25

我需要的比这个高啊
就要满bit的

呵呵
为了顺便测试那个bit索引算法

mathe 发表于 2008-3-17 09:49:34

不过通常周期长的伪随机序列计算复杂度也要大一些。
如果为了测试那个bit索引算法，使用太复杂的伪随机序列产生程序，这部分代码所占用时间太长，会对那部分代码的时间测试影响太大。

无心人 发表于 2008-3-17 09:51:36

Cache下来啊
我先填充100万测试数据

实在没办法就用位随机算法产生10万数据先凑合下
头疼位随机的恐怖执行时间

mathe 发表于 2008-3-17 09:56:13

产生数据不是问题，使用线性移位寄存器产生M序列应该是一种可取的办法。
不过实现产生100万数据，对内存压力比较大。测试中很多时间是花费在读取内存上的。4Mega的数据通常L2 Cache都会装不下，访问内存花费的时间比例太高了。

无心人 发表于 2008-3-17 09:59:48

那考虑10万的？

mathe 发表于 2008-3-17 10:03:46

10万应该好一些，通常L2 Cache都应该装的下，不过L1Cache会装不下，但是对于顺序访问，通常硬件会自动做数据预取，但是就不知道对于这种情况会做的多好，毕竟访问L2 Cache的速度还是比较慢的（可能略小于10个时钟周期吧）。

无心人 发表于 2008-3-17 10:05:56

先写了个位算法
不知可行么
编译去DWORD BitRandom(void)
{
        __asm
        {
        mov ecx, 31
        mov edx, 0
loop1:
        call rand
        andeax, 1
        shl eax, cl
        add edx, eax
        sub ecx, 1
        jnc loop1
        mov eax, edx
        }
}

mathe 发表于 2008-3-17 10:10:14

call rand占用的时间比例太高。这个很难去评测除掉函数调用以后部分代码占用的时间周期。

查看完整版本: 求随机产生0-2^32-1内整数算法