求随机产生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占用的时间比例太高。这个很难去评测除掉函数调用以后部分代码占用的时间周期。