使用按位＆放大器;而不是模运算符随机从一系列整数取样 [英] Using bitwise & instead of modulus operator to randomly sample integers from a range

问题描述

我需要一个整数的均匀分布在C间隔 [LB，UB] ++随机抽样。要做到这一点，我开始一个好RN发生器，均匀随机采样64位整数（从数字食谱第3版）;让我们叫它的Int64（）。

I need to randomly sample from a uniform distribution of integers over the interval [LB,UB] in C++. To do so, I start with a "good" RN generator (from Numerical Recipes 3rd ed.) that uniformly randomly samples 64-bit integers; let's call it int64().

使用Mod运算符，我可以在从整数样[LB，UB] 按

Using the mod operator, I can sample from the integers in [LB,UB] by:

LB+int64()%(UB-LB+1);

使用Mod运算符的唯一问题是整数除法的缓慢。于是，我又试图方法建议这里，那就是：

LB + (int64()&(UB-LB))

按位与放大器;方法为约3倍的速度。这是巨大的我，因为我用C ++模拟一个需要随机抽样约2000万的整数。

The bitwise & method is about 3 times as fast. This is huge for me, because one of my simulations in C++ needs to randomly sample about 20 million integers.

但是，还有1大问题。当我分析了使用位和放采样的整数;方法，它们不会出现均匀地间隔分布 [LB，UB] 。该整数确实是从 [LB，UB] ，但抽样的从该范围内的偶数唯一。例如，下面是使用位和放大器在[20,50]采样5000整数直方图;方法：

But there's 1 big problem. When I analyze the integers sampled using the bitwise & method, they don't appear uniformly distributed over the interval [LB,UB]. The integers are indeed sampled from [LB,UB], but only from the even integers in that range. For example, here is a histogram of 5000 integers sampled from [20,50] using the bitwise & method:

相比之下，这里是一个类似的直方图看起来使用Mod运算符方法，这当然正常工作时，如：

By comparison, here is what a similar histogram looks like when using the mod operator method, which of course works fine:

这有什么错我的按位＆安培;方法？有什么办法来修改它，使偶数和奇数号码在定义的时间间隔取样？

What's wrong with my bitwise & method? Is there any way to modify it so that both even and odd numbers are sampled over the defined interval?

推荐答案

按位＆安培; 运营商着眼于每对相应操作数的位数，执行和只使用两个位，并提出在导致结果的对应位

The bitwise & operator looks at each pair of corresponding bits of its operands, performs an and using only those two bits, and puts that result in the corresponding bit of the result.

所以，如果 UB-LB 的最后一位是0，那么结果的最后一位是 0 。也就是说，如果 UB-LB 是即使这样每个输出将是偶数。

So, if the last bit of UB-LB is 0, then the last bit of the result is 0. That is to say, if UB-LB is even then every output will be even.

的＆安培; 是不合适的目的，除非 UB-LB + 1 是2的力量。如果你想找到一个模数，那么就没有常规快捷：编译器将已经实施％它知道的最快方法

The & is inappropriate to the purpose, unless UB-LB+1 is a power of 2. If you want to find a modulus, then there's no general shortcut: the compiler will already implement % the fastest way it knows.

请注意，我说没有的一般的快捷方式。对于 UB-LB 的特定值，在编译时已知，可以有更快的方式。如果你能以某种方式安排 UB 和 LB 有编译器可以在编译时计算那么它将值使用它们，当你写％。

Note that I said no general shortcut. For particular values of UB-LB, known at compile time, there can be faster ways. And if you can somehow arrange for UB and LB to have values that the compiler can compute at compile time then it will use them when you write %.

顺便说一下，使用％事实上并不产生均匀分布的整数以上的范围内，除非该范围的大小是2的幂否则，必须赞成某些值略有偏差，因为你的 64位整数的范围（）功能无法跨越所需范围同样分配。这可能是二者差距太小而影响尤其是你的模拟，但糟糕的随机数生成器在过去的破碎随机模拟，并会再次这样做。

By the way, using % does not in fact produce uniformly-distributed integers over the range, unless the size of the range is a power of 2. Otherwise there must be a slight bias in favour of certain values, because the range of your int64() function cannot be assigned equally across the desired range. It may be that the bias is too small to affect your simulation in particular, but bad random number generators have broken random simulations in the past, and will do so again.

如果你想在任意范围内的均匀随机数的分布，然后用的std :: uniform_int_distribution 从C ++ 11或类升压同名

If you want a uniform random number distribution over an arbitrary range, then use std::uniform_int_distribution from C++11, or the class of the same name in Boost.

这篇关于使用按位＆放大器;而不是模运算符随机从一系列整数取样的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！