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

无心人

要求速度快 且满足概率意义上的平均分布 即假设产生100万数据 如果平均切分[0, 2^32-1]区间为10份 则每个区间的数字个数都要接近10万 总偏差不能超过10% 同样道理， 做其他等分切分 则区间分布偏差也要小

gxqcn

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

无心人

我需要的比这个高啊 就要满bit的 呵呵 为了顺便测试那个bit索引算法

mathe

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

无心人

Cache下来啊 我先填充100万测试数据 实在没办法就用位随机算法产生10万数据先凑合下 头疼位随机的恐怖执行时间

mathe

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

无心人

那考虑10万的？

mathe

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

无心人

先写了个位算法 不知可行么 编译去

1. DWORD BitRandom(void)
2. {
3. __asm
4. {
5. mov ecx, 31
6. mov edx, 0
7. loop1:
8. call rand
9. and eax, 1
10. shl eax, cl
11. add edx, eax
12. sub ecx, 1
13. jnc loop1
14. mov eax, edx
15. }
16. }

复制代码

mathe

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