RAND_MAX和UINT_MAX之间的差异会有所不同吗？

Question

我的作业包括在0和之间制作随机整数2^30.现在,在过去,我们已经知道rand()只返回整数RAND_MAX,这小于UINT_MAX,并且我们可以使用位移来填充该UINT_MAX容量.从我已经完成的一些阅读(这里,在SO上),我意识到,如果这些数字的分布对我很重要,这可能不是一个好主意.话虽如此,我的教授已经指明了这种方法.

我的问题是,转移多少钱？将之间的区别RAND_MAX,并UINT_MAX一直是这样的,有一个安全的常量,其中位移位？或者是否需要进行一些初步探测以确定位移的数量？我应该保持一点点移位并检查一下UINT_MAX吗？

我问的原因是,UINT_MAX定义为至少某个数字(65535),但在我的机器UINT_MAX上要大得多(4294967295).这让我担心我可能会在周末完成作业,到学校,并发现一切都不能很好地提交.

谢谢!

参考文献:

我读过几个类似的问题,但无法从中获得答案.

RAND_MAX永远的价值是(2^n)-1什么？

产生范围内的随机数0,以n在那里n可> RAND_MAX

实际上,上面的第二个问题让我质疑这样做的价值吗？

Answer 1

你的问题主要围绕是否RAND_MAX和UINT_MAX它们之间的比特移位.这减少了形式是否UINT_MAX和RAND_MAX形式的问题2^k - 1.UINT_MAX几乎肯定会在任何基于二进制数系统的计算机上.如果是sizeof(int)=32那么k=32,如果sizeof(int)=64 bit那么k=64,等等.现在我们可以考虑了RAND_MAX.在大多数实现中,答案是RAND_MAX几乎总是形式的2^k - 1.为什么？我们需要考虑大多数实现的rand()实际工作方式.

1. rand()通常使用线性同余生成器(参见http://en.wikipedia.org/wiki/Linear_congruential_generator或Knuth"计算机程序员的艺术第2部分:半数值算法").基本上随机数是带有a的序列seed

   x(k + 1)=(ax(k)+ c)%m

(即C库存储最后一次迭代x(k),当你调用rand()它时返回x(k+1))

1. 要质量好,发电机(参数a,c和m)必须慎重选择.质量通常需要在序列重复之前多少次,等等.选择这些参数的一个紧张是m尽可能接近,UINT_MAX以避免浪费潜在的随机位.如果你研究发电机,通常正确的选择是做m一些小于UINT_MAX.你还需要做m一个素数.

2. 通常,您希望rand()尽可能快,以便您希望这些操作便宜.mod计算最便宜的是其中一种形式, foo % (2^k - 1)因为它可以实现为foo & (1<<k-1).k如果您有特别的选择,您将获得Mersenne prime.

例如,一个共同的选择是k=31产生素数2^31-1 = 2147483647.这是32位整数的典型选择UINT_MAX=2^32-1 = 4294967295.对于64位数字UINT_MAX=2^64-1=18446744073709551615,可以选择RAND_MAX 2^61-1 = 2305843009213693951.

总而言之,回答你的问题:在大多数实现中你可以假设有一个简单的位移,但是,没有真正的保证.至少你应该在你的程序init上进行运行时测试.如果您正在使用C++,更好的做法是使用a static_assert在编译时检测您的假设是否为真,如果不是则无法编译.Boost有这样的静态断言,就像最近批准的标准C++ 11一样......即可以做到(尽管编写静态版本可能需要一些工作is_power_of_two_minus_one):

unsigned int myrand()
{
        static_assert(sizeof(int)==4,"sizeof(unsigned int) != 4");
        static_assert(is_power_of_two_minus_one(RAND_MAX),"RAND_MAX not a power of two minus one");
        static_assert(is_power_of_two_minus_one(UINT_MAX),"UINT_MAX not power of two minus one");
        unsigned int raw_rand=rand();
        // do your bit shift to adjust raw_rand
        return raw_rand;
}